COGS577

CDQ分治

const int maxn = 2e5+100;
const int maxm = 5e5+100;
int n,w;
int tree[maxn];
void Add(int p,int x){
    while(p <= w){
        tree[p] += x;
        p += lowbit(p);
    }
}
int Sum(int p){
    int sum = 0;
    while(p > 0){
        sum += tree[p];
        p -= lowbit(p);
    }
    return sum;
}

struct nd{
    int x1,y1,x2,y2,z,id,op;
};
bool operator <(const nd &a,const nd &b){
    return (a.x1 < b.x1)||(a.x1==b.x1&&a.op < b.op);
}
nd A[maxm],B[maxm];

int ans[maxn];
void CDQ(int L,int R){
    if(L == R) return ;
    int M = (L+R)>>1;
    CDQ(L,M);CDQ(M+1,R);
    int cnt = 0;
    for(int i = L;i <= M; ++i)
        if(A[i].op == 1) 
            B[cnt++] = A[i];
    for(int i = M+1;i <= R; ++i)
        if(A[i].op == 2)
            {
                B[cnt] = A[i];B[cnt].x1--,cnt++;
                B[cnt] = A[i];B[cnt].x1 = B[cnt].x2,B[cnt].op =3,cnt++;
            }

    sort(B,B+cnt);
    for(int i = 0;i < cnt; ++i){
        if(B[i].op == 1)        Add(B[i].y1,B[i].z);
        else if(B[i].op == 2)   ans[B[i].id] -= Sum(B[i].y2)-Sum(B[i].y1-1);
        else                    ans[B[i].id] += Sum(B[i].y2)-Sum(B[i].y1-1);
    }

}
int main(void){

    scanf("%d%d",&w,&n);

    for(int i = 1;i <= n; ++i){
        scanf("%d",&A[i].op);
        if(A[i].op == 1) scanf("%d%d%d",&A[i].x1,&A[i].y1,&A[i].z);
        else scanf("%d%d%d%d",&A[i].x1,&A[i].y1,&A[i].x2,&A[i].y2);
        A[i].id = i;
    }
    CDQ(1,n);

    for(int i = 1;i <= n; ++i){
        if(A[i].op == 2)
            printf("%d\n",ans[A[i].id]);
    }
}