Submission

PPPPPPPPPPPPPPPPPPPP

Score: 100

User: mydKN

Problemset: ผลบวก (ยาก)

Language: cpp

Time: 0.080 second

Submitted On: 2025-04-19 02:00:16

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5;

int n, q;
int arr[maxn];
int t[4 * maxn];

void build(int idx, int tl, int tr){
	if(tl == tr) t[idx] = arr[tl];
	else{
		int tm = (tl + tr) >> 1;
		build(idx*2, tl, tm);
		build(idx*2+1, tm+1, tr);
		t[idx] = t[idx*2] + t[idx*2+1];
	}
}

int qr(int idx, int tl, int tr, int l, int r){
	if(tl > r || tr < l) return 0;
	if(tl >= l && tr <= r) return t[idx];
	int tm = (tl + tr) >> 1;
	return qr(idx*2, tl, tm, l, r) + qr(idx*2+1, tm+1, tr, l, r);
}

void update(int idx, int tl, int tr, int pos, int val){
	if(tl == tr){
		t[idx] = val;
		arr[pos] = val;
	}
	else{
		int tm = (tl + tr) >> 1;
		if(pos > tm) update(idx*2+1, tm+1, tr, pos, val);
		else update(idx*2, tl, tm, pos, val);
		t[idx] = t[idx*2] + t[idx*2+1];
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;++i){
		cin >> arr[i];
	}
	build(1, 1, n);
	cin >> q;
	while(q--){
		int t;
		cin >> t;
		while(t--){
			int x, val;
			cin >> x >> val;
			++x;
			update(1, 1, n, x, val);
		}
		int x, y;
		cin >> x >> y;
		cout << qr(1, 1, n, x+1, y+1) << "\n";
	}
}