-
Notifications
You must be signed in to change notification settings - Fork 6
/
CanYouAnswerTheseQueries5.cpp
115 lines (100 loc) · 2.99 KB
/
CanYouAnswerTheseQueries5.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <unistd.h>
#include <vector>
#include <algorithm>
#define SIZE 10001
struct Node {
int sum, maxSum, prefixSum, suffixSum;
Node() : sum(0), maxSum(0), prefixSum(0), suffixSum(0) { }
Node(int sum, int maxSum, int prefixSum, int suffixSum) {
this->sum = sum;
this->maxSum = maxSum;
this->prefixSum = prefixSum;
this->suffixSum = suffixSum;
}
static Node nullNode;
};
Node Node::nullNode;
class SegmentTree {
Node tree[4*SIZE];
int parents[SIZE], size;
std::vector<int> elements;
Node mergeNodes(Node a, Node b) {
Node res;
res.sum = a.sum + b.sum;
res.maxSum = std::max(
std::max(a.maxSum, b.maxSum),
a.suffixSum + b.prefixSum
);
res.prefixSum = std::max(a.prefixSum, a.sum + b.prefixSum);
res.suffixSum = std::max(b.suffixSum, b.sum + a.suffixSum);
return res;
}
public:
SegmentTree(std::vector<int> arr) : size(arr.size()) {
elements = arr;
buildTree(0, 0, size-1);
}
void buildTree(int curNode, int start, int end) {
if(start == end) {
tree[curNode].prefixSum = tree[curNode].suffixSum = tree[curNode].sum = tree[curNode].maxSum = elements[start];
parents[start] = curNode;
}
else {
int l = curNode * 2 + 1;
int r = curNode * 2 + 2;
int mid = (start + end)/2;
buildTree(l, start, mid);
buildTree(r, mid+1, end);
tree[curNode] = mergeNodes(tree[l], tree[r]);
}
}
Node query(int curNode, int start, int end, int qx, int qy) {
if(qx > qy) return Node::nullNode;
if(qx == start && end == qy) return tree[curNode];
int l = curNode*2 + 1;
int r = curNode*2 + 2;
int mid = (start+end)/2;
if(qy <= mid)
return query(l, start, mid, qx, qy);
else if(qx > mid)
return query(r, mid+1, end, qx, qy);
else
return mergeNodes(query(l, start, mid, qx, mid), query(r, mid+1, end, mid+1, qy));
}
};
int main() {
int T;
scanf("%d", &T);
while(T--) {
int N, Q;
scanf("%d", &N);
std::vector<int> aList(N);
for(int i = 0; i < N; i++)
scanf("%d", &aList[i]);
SegmentTree aSegTree(aList);
int ans;
scanf("%d", &Q);
while(Q--) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
x1--, y1--, x2--, y2--;
if(y1 < x2) { /* disjoint */
ans = aSegTree.query(0, 0, N-1, x1, y1).suffixSum +
aSegTree.query(0, 0, N-1, y1+1, x2-1).sum +
aSegTree.query(0, 0, N-1, x2, y2).prefixSum;
}
else { /* joint */
ans = std::max(
aSegTree.query(0, 0, N-1, x2, y1).maxSum,
std::max(
aSegTree.query(0, 0, N-1, x1, x2-1).suffixSum + aSegTree.query(0, 0, N-1, x2, y2).prefixSum,
aSegTree.query(0, 0, N-1, x1, y1).suffixSum + aSegTree.query(0, 0, N-1, y1+1, y2).prefixSum
)
);
}
printf("%d\n", ans);
}
}
return 0;
}