仍然是一道cdq模版。。
那么对于一个询问，容斥一下分成四个，变成问(1,1)~(x,y)，那么对于x,y，修改只有x'<=x&&y'<=y，才对询问有影响，那么加上读入顺序，就是一个三维偏序了。
#include#include #include #include #include #include using namespace std;struct node{ int tp,x,y,v,be;//第一维时间已经有序 //tp=0 表示修改 v为修改的值 //tp=-1、1询问 v为所求值 }a[210000];int len;void ins(int tp,int x,int y,int v,int be){ len++; a[len].tp=tp; a[len].x=x;a[len].y=y; a[len].v=v;a[len].be=be;}//----------------------------------int n,s[2100000];int lowbit(int x){ return x&-x;}void add(int x,int k){ while(x<=n) { s[x]+=k; x+=lowbit(x); }}int getsum(int x){ int ans=0; while(x>=1) { ans+=s[x]; x-=lowbit(x); } return ans;}//---------------树状数组----------------- node t[210000];void cdq(int l,int r){ if(l==r)return ; int mid=(l+r)/2; cdq(l,mid); cdq(mid+1,r); int i=l,j=mid+1,p=l; while(i<=mid&&j<=r) { if(a[i].x<=a[j].x) { if(a[i].tp==0)add(a[i].y,a[i].v); t[p++]=a[i++]; } else { if(a[j].tp!=0)a[j].v+=getsum(a[j].y); t[p++]=a[j++]; } } while(i<=mid) { if(a[i].tp==0)add(a[i].y,a[i].v); t[p++]=a[i++]; } while(j<=r) { if(a[j].tp!=0)a[j].v+=getsum(a[j].y); t[p++]=a[j++]; } for(int i=l;i<=mid;i++) if(a[i].tp==0)add(a[i].y,-a[i].v); for(int i=l;i<=r;i++)a[i]=t[i];}//-------------------cdq------------------------ int ans[11000],ansl;int main(){ int S; scanf("%d%d",&S,&n); int op,x1,y1,x2,y2,v;len=0; while(scanf("%d",&op)!=EOF) { if(op==3)break; if(op==1) { scanf("%d%d%d",&x1,&y1,&v); ins(0,x1,y1,v,0); } else { ansl++; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(x1-1>0&&y1-1>0)ins(1,x1-1,y1-1,0,ansl); if(x1-1>0)ins(-1,x1-1,y2,0,ansl); if(y1-1>0)ins(-1,x2,y1-1,0,ansl); ins(1,x2,y2,0,ansl); } } cdq(1,len); memset(ans,0,sizeof(ans)); for(int i=1;i<=len;i++) if(a[i].tp!=0)ans[a[i].be]+=a[i].v*a[i].tp; for(int i=1;i<=ansl;i++)printf("%d\n",ans[i]); return 0;}