Lvat_s Blog

CDQ分治

递归处理左边的操作，再计算影响，然后处理右边的操作。

使用一个树状数组，利用排序x坐标的单调性，然后直接在树状数组上操作就行了。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
struct Do{
int flag,x,y,id,v,pos;
friend bool operator <(const Do &a,const Do &b){
return a.x==b.x?(a.y==b.y?a.pos<b.pos:a.y<b.y):a.x<b.x;
}
}Q[200005],tmp[200005];
 
int s,w,tot,_Y[210005],toty,ans[10005],totans,BIT[200005],t1,t2,cnt;
 
int lowbit(int x){
return x&(-x);
}
 
void Add(int pos,int val){
while(pos<=toty){
    BIT[pos]+=val;
    pos+=lowbit(pos);
}
}
 
int Query(int pos){
int ans=0;
while(pos){
    ans+=BIT[pos];
    pos-=lowbit(pos);
}
return ans;
}
 
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1,t1=l,t2=mid+1;
for(int i=l;i<=r;i++){
    //printf("Hello!:%d %d %d %d %d\n",Q[i].id,mid,Q[i].flag,Q[i].fg,Q[i].pos);
    if(Q[i].id<=mid && Q[i].flag==1){Add(Q[i].y,Q[i].v);/*printf("Reggle:%d %d\n",Query(Q[i].y),Q[i].v);*/}
    if(Q[i].id>mid && Q[i].flag==2){/*puts("233");printf("Leggle:%d\n",Query(Q[i].y));*/ans[Q[i].pos]+=Q[i].v*Query(Q[i].y);}
}
for(int i=l;i<=r;i++){
    if(Q[i].id<=mid && Q[i].flag==1)Add(Q[i].y,-Q[i].v);
}
for(int i=l;i<=r;i++){
    if(Q[i].id<=mid)tmp[t1++]=Q[i];
    else tmp[t2++]=Q[i];
}
for(int i=l;i<=r;i++){
    Q[i]=tmp[i];
}
CDQ(l,mid);
CDQ(mid+1,r);
}
 
int main(){
freopen("1176.in","r",stdin);
freopen("1176.out","w",stdout);
scanf("%d %d",&s,&w);
while(scanf("%d",&Q[++tot].flag)!=EOF){
    if(Q[tot].flag==3){tot--;break;}
    if(Q[tot].flag==1){
        scanf("%d %d %d",&Q[tot].x,&Q[tot].y,&Q[tot].v);
        _Y[++toty]=Q[tot].y;
        Q[tot].id=tot;
        Q[tot].pos=0;
    }
    else {
        int x1,x2,y1,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        ans[++cnt]=s*(x2-x1+1)*(y2-y1+1);
        Q[tot].x=x1-1;
        Q[tot].y=y1-1;
        Q[tot].id=tot;
        Q[tot].pos=cnt;
        Q[tot].v=1;
        _Y[++toty]=Q[tot].y;
        tot++;
        Q[tot].flag=2;
        Q[tot].x=x2;
        Q[tot].y=y1-1;
        Q[tot].id=tot;
        Q[tot].pos=cnt;
        Q[tot].v=-1;
        tot++;
        Q[tot].flag=2;
        Q[tot].x=x1-1;
        Q[tot].y=y2;
        Q[tot].id=tot;
        _Y[++toty]=Q[tot].y;
        Q[tot].pos=cnt;
        Q[tot].v=-1;
        tot++;
        Q[tot].flag=2;
        Q[tot].x=x2;
        Q[tot].y=y2;
        Q[tot].pos=cnt;
        Q[tot].id=tot;
        Q[tot].v=1;
    }
}
sort(_Y+1,_Y+toty+1);
toty=unique(_Y+1,_Y+toty+1)-_Y-1;
for(int i=1;i<=tot;i++){
    Q[i].y=lower_bound(_Y+1,_Y+toty+1,Q[i].y)-_Y;
}
sort(Q+1,Q+tot+1);
CDQ(1,tot);
for(int i=1;i<=cnt;i++){
    printf("%d\n",ans[i]);
}
return 0;
}