Submission

P-PPPPPPPPPPPPPPPPPP

Score: 95

User: Khiem

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

Language: cpp

Time: 0.107 second

Submitted On: 2024-09-29 17:10:48

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
signed main(){
	int n; scanf("%d", &n);
	vector<ll>a(n+1);
	vector<ll>bit(n+1, 0);
	for(int i = 1; i<=n; ++i){
		ll x; scanf("%lld", &x);
		for(int j = i; j<=n; j+=j&-j) bit[j] += x;
		a[i] = x;
	}
	int q; scanf("%d", &q);
	while(q--){
		int t; scanf("%d", &t);
		while(t--){
			int i; ll v; scanf("%d %lld", &i, &v); ++i; 
			for(int j = i; j<=n; j+=j&-j) bit[j] += v-a[i];
			a[i] = v; 
		}
		int x, y; scanf("%d %d", &x, &y); ++x; ++y; if(x > y) swap(x, y);
		ll r = 0;
		for(--x; x; x-=x&-x) r -= bit[x];
		for(; y; y-=y&-y) r += bit[y];
		printf("%lld\n", r);
	}
}