KGSS - Maximum Sum
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
const int N = 1e5;
int t[4*N][2], n, a[N], temp[4];
void update(int k, int l, int r, int u, int val) {
if(l > r || u < l || u > r) return;
if(l == r) {
t[k][0] += val;
t[k][1] = INT_MIN;
} else {
update(2*k+1, l, (l+r)/2, u, val);
update(2*k+2, (l+r)/2+1, r, u, val);
temp[0] = t[2*k+1][0]; temp[1] = t[2*k+1][1];
temp[2] = t[2*k+2][0]; temp[3] = t[2*k+2][1];
sort(temp, temp+4);
t[k][0] = temp[3]; t[k][1] = temp[2];
}
}
pair<int, int> get(int k, int l, int r, int u, int v) {
if(l > r || v < l || r < u) return make_pair(INT_MIN, INT_MIN);
if(u <= l && r <= v) return make_pair(t[k][0], t[k][1]);
pair<int, int> p1 = get(2*k+1, l, (l+r)/2, u, v);
pair<int, int> p2 = get(2*k+2, (l+r)/2+1, r, u, v);
temp[0] = p1.first; temp[1] = p1.second;
temp[2] = p2.first; temp[3] = p2.second;
sort(temp, temp+4);
return make_pair(temp[3], temp[2]);
}
int sum(const pair<int, int> &p) {
return p.first + p.second;
}
int main() {
int n; scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
update(0, 0, n-1, i, a[i]);
}
int q; scanf("%d", &q);
for(int i = 0; i < q; ++i) {
char c; int x, y;
scanf(" %c%d%d", &c, &x, &y);
if(c == 'U') {
update(0, 0, n-1, x-1, y - a[x-1]);
a[x-1] = y;
} else printf("%d\n", sum(get(0, 0, n-1, x-1, y-1)));
}
return 0;
}