题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

输入格式

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数，表示一个操作，具体如下：

操作1： 格式：1 x k 含义：将第x个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

代码

#include
    
     using namespace std;前提是可以离线查询，也就是先询问然后最后统一输出答案 主要用了分治的思想，先对子区间进行求解，然后合并的时候计算左区间对右区间的贡献最后就可以得出答案了 #define sc scanf#define pr printf#define rep(i,x,y) for(int i = x;i <= y;i++)#define rvp(i,x,y) for(int i = y;i >= x;i--)int tot = 0,cnt = 0;typedef long long ll;const int N = 5e5 + 10;ll ans[N];struct node{    int id,type;    ll va;    bool operator < (const node &a) const    {        if(id != a.id) return id < a.id;        else return type < a.type;    }}; node A[N*4],B[N*4];void CDQ(int l,int r){    if(l==r) return;    int m = (l+r) >> 1;    CDQ(l,m);    CDQ(m+1,r);    int p1 = l,p2 = m+1;    ll sum = 0;    rep(i,l,r)    {        if(p2 > r || p1 <= m && A[p1] < A[p2])        {            if(A[p1].type == 1) sum += A[p1].va;//计算左区间对右区间的贡献             B[i] = A[p1++];        }        else{            //类似前缀和的思想             if(A[p2].type == 2) ans[A[p2].va] -= sum;            else if(A[p2].type == 3) ans[A[p2].va] += sum;            B[i] = A[p2++];        }    }    rep(i,l,r) A[i] = B[i];}int main(){    int n,m;    sc("%d%d",&n,&m);    rep(i,1,n)    {        tot++;        A[tot].id = i; A[tot].type = 1;        sc("%lld",&A[tot].va);    }    rep(i,1,m)    {        tot++;        int op;        sc("%d",&op);        if(op==1){            A[tot].type = op;            sc("%d%lld",&A[tot].id,&A[tot].va);        }        else{            int l,r;            sc("%d%d",&l,&r);            cnt++;            A[tot].type = 2; A[tot].va = cnt; A[tot].id = l - 1;            tot++;            A[tot].type = 3; A[tot].va = cnt; A[tot].id = r;        }    }    CDQ(1,tot);    rep(i,1,cnt) pr("%lld\n",ans[i]);    return 0;}