Submission

PP------------------

Score: 10

User: tull

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

Language: cpp

Time: 0.064 second

Submitted On: 2025-04-12 04:54:04

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ll long long
template <class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
using pil=pair<int,long long>;
using pli=pair<long long,int>;
using pll=pair<long long,long long>;
using pii=pair<int,int>;
using piii=pair<pair<int,int>,int>;
using plll=pair<pair<ll,ll>,ll>;
using pic=pair<int,char>;
const int MX= 1000000000000000000LL; //1e18
const int MN=-MX; //-1e18
const int MOD = 1e9+7;
#define bp '\n'
#define ull unsigned long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define inv(a) for(auto&e:a){cin>>e;}
#define vp cout<<'\n';
#define inv2dm(a) for(auto&e:a)for(auto&c:e)cin>>c;
#define ck(a) for(auto&e:a)cout<<e<<' ';cout<<'\n';
#define ckpf(a) for(auto&e:a)printf("%d ",e);printf("\n");
#define ckpair(a) for(auto&[f,s]:a)cout<<"("<<f<<", "<<s<<") ";cout<<'\n';
#define LMX LLONG_MAX
#define LMN LLONG_MIN
#define ck2dm(a) cout<<'\n';for(auto&e:a){for(auto&c:e)cout<<((c==MX or c==MN)?9:c)<<' ';cout<<'\n';}
#define ck2dmlr(a,l,r) cout<<'\n';for(int i=0;i<l;++i){for(int j=0;j<r;++j){cout<<((a[i][j]==MN or a[i][j]==MX)?9:a[i][j])<<'\t';}cout<<'\n';}
#define tostr(a) to_string(a)
#define qs(a) for(int i=1;i<a.size();++i)a[i]+=a[i-1];
#define vpii vector<pair<int,int>>
#define dir vector<pair<int,int>>direct={{-1,0},{1,0},{0,1},{0,-1}};
#define val(i,j) (i>=0 and i<n and j>=0 and j<m)?1:0
#define vi vector<int>
#define mt make_tuple
#define mp make_pair
#define db double
int fen[1000000+5],def[1000000+5];
int n,l,r,q,x;
void add(int i,int a){
    for(;i<n;i+=i&-i){
        fen[i]+=a;
    }
}
void cn(int l,int r){
    int d=r-def[l];
    def[l]=r;
    //int s=0;
    for(;l<n;l+=l&-l){
        fen[l]+=d;
    }
}
int sum(int l,int r){
    int s=0;
    for(;r>0;r-=r&-r){
        s+=fen[r];
    }
    for(l-=1;l>0;l-=l&-l){
        s-=fen[l];
    }
    return s;
}
signed main(){
    //freopen("test_input.txt","r",stdin);
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>x;
        def[i]=x;
        add(i,x);
    }
    cin>>q;
    while(q--){
        cin>>x;
        while(x--){
            cin>>l>>r;
            cn(l+1,r);
        }
        cin>>l>>r;
        cout<<sum(l+1,r+1)<<bp;
    }
    return 0;
}