Submission

PPPPPPPPPPPPPPPPPPPP

Score: 100

User: mydKN

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

Language: cpp

Time: 0.072 second

Submitted On: 2024-11-09 00:35:36

#include<bits/stdc++.h>

using namespace std;

#define maxnode 2097161
#define maxn 1000010

int sum[maxnode];
int arr[maxn];

void push(int root){
    sum[root] = sum[root*2] + sum[root*2+1];
}

void build(int root, int l, int r){
    if(l == r){
        sum[root] = arr[l];
    }
    else{
        int mid = (l+r)/2;
        build(root*2, l, mid);
        build(root*2+1, mid+1, r);
        push(root);
    }
}

int query(int root, int l, int r, int ql, int qr){
    if(r < ql || l > qr) return 0;
    if(l >= ql && r <= qr) return sum[root];
    int m = (l+r)/2;
    return query(root*2, l, m, ql, qr) + query(root*2+1, m+1, r, ql, qr);
}

void update(int root, int l, int r, int pos, int val){
    if(l == r){
        sum[root] += val;
        arr[pos] += val;
        return;
    }
    int m = (l+r)/2;
    if(l <= pos && pos <= m) update(root*2, l, m, pos, val);
    else if(m <= pos && pos <= r) update(root*2+1, m+1, r, pos, val);
    push(root);
}

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

/*
// cout << query(1, 1, n, 3, 5);
8
2 5 7 9 6 8 1 3
*/