Submission

PPPPPPPPPPPPPPPPPPPP

Score: 100

User: a0ms1n

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

Language: cpp

Time: 0.074 second

Submitted On: 2024-12-04 12:41:41

#include <bits/stdc++.h>
using namespace std;
typedef long long ii;

ii darr[(int)1e4+1]={0};
ii arr[(int)1e6+1]={0};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    int dsiz = sqrt(n+.0)+1;  

    for(int i=0;i<n;i++){
        cin>>arr[i];
        darr[i/dsiz]+=arr[i];
    }
    int q;cin>>q;
    while(q--){
        int t;cin>>t;
        while(t--){
            ii idx,val; cin>>idx>>val;
            darr[idx/dsiz] += val-arr[idx];
            arr[idx] = val;
        }
        int a,b;cin>>a>>b;
        int ca = a/dsiz + (a%dsiz != 0),cb=b/dsiz;
        ii sum = 0;
        if(ca>=cb)for(int i=a;i<=b;i++)sum+=arr[i];
        else{
            for(int i=a,end=ca*dsiz;i<end;i++)sum+=arr[i];
            for(int i=ca;i<cb;i++)sum+=darr[i];
            for(int i=cb*dsiz;i<=b;i++)sum+=arr[i];
        }
        cout<<sum<<'\n';
    }

    return 0;
}