Submission

PPPPPPPPPPPPPPPPPPPP

Score: 100

User: Newtonabc

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

Language: cpp

Time: 0.080 second

Submitted On: 2024-09-30 21:21:25

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int M=1<<21;
int arr[N],s[M];
void build(int l,int r,int idx){
	if(l==r){
		s[idx]=arr[l];
		return;
	}
	int m=(l+r)/2;
	build(l,m,idx*2);
	build(m+1,r,idx*2+1);
	s[idx]=s[idx*2]+s[idx*2+1];
}
void update(int l,int r,int idx,int x,int val){
	if(x<l || x>r) return;
	if(l==r){
		s[idx]=val;
		return;
	}
	int m=(l+r)/2;
	update(l,m,idx*2,x,val);
	update(m+1,r,idx*2+1,x,val);
	s[idx]=s[idx*2]+s[idx*2+1];
}
int query(int l,int r,int idx,int a,int b){
	if(b<l || a>r) return 0;
	if(a<=l && b>=r) return s[idx];
	int m=(l+r)/2;
	return query(l,m,idx*2,a,b)+query(m+1,r,idx*2+1,a,b);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	build(0,n-1,1);
	cin>>q;
	while(q--){
		int t,ta,tb;
		cin>>t;
		while(t--){
			int a,b;
			cin>>a >>b;
			update(0,n-1,1,a,b);
		}
		cin>>ta >>tb;
		cout<<query(0,n-1,1,ta,tb) <<"\n";
	}
}