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;
}

Download