bzoj2683 简单题

2683: 简单题

Time Limit: 50 Sec  Memory Limit: 128 MB Submit: 1282  Solved: 510 [ Submit][ Status][ Discuss]

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

 

命令

参数限制

内容

1 x y A

1<=x,y<=N，A是正整数

将格子x,y里的数字加上A

2 x₁ y₁ x₂ y₂

1<=x₁<= x₂<=N

1<=y₁<= y₂<=N

输出x₁ y₁ x₂ y₂这个矩形内的数字和

3

无

终止程序

Input

输入文件第一行一个正整数N。 接下来每行一个操作。  

Output

对于每个2操作，输出一个对应的答案。  

Sample Input

4 1 2 3 3 2 1 1 3 3 1 2 2 2 2 2 2 3 4 3

Sample Output

3 5

HINT

 

1<=N<=500000,操作数不超过200000个，内存限制20M。 对于100%的数据，操作1中的A不超过2000。

 

其实这题的算法挺好理解的，CDQ二分

子矩阵的数字和表示为 s(x1,y1,x2,y2)=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]

因此一个要查询的子矩阵，对其有影响的矩阵为s[x2][y2]，s[x2][y1-1]，s[x1-1][y2]，s[x1-1][y1-1]这四个前缀子矩阵

按题目的意思，是要求我们在线做，但是CDQ算法不乐意在线做

于是要注意到操作顺序，位置顺序两个东西

至于位置顺序，它是二维的，不妨把x从小到大排个序，然后对y进行树状数组搞个前缀和，再用

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct node{ int x,y,z,b,p,t; }q[200010*4],tmp[200010*4]; int n,tot,t,sum[200010*4],ans[200010*4]; int cmp(node i,node j){ if(i.x==j.x&&i.y==j.y)return i.p<j.p; if(i.x==j.x)return i.y<j.y; return i.x<j.x; } void add(int x,int y){ while(x<=n)sum[x]+=y,x+=x&-x; } int getsum(int x){ int result=0; while(x>0)result+=sum[x],x-=x&-x; return result; } void work(int l,int r){ if(l==r)return; int mid=(l+r)>>1; int ll=l,rr=mid+1; for(int i=l;i<=r;i++){ if(q[i].t<=mid&&q[i].p==1)add(q[i].y,q[i].z); if(q[i].t>mid&&q[i].p==2)ans[q[i].b]+=getsum(q[i].y)*q[i].z; } for(int i=l;i<=r;i++) if(q[i].t<=mid&&q[i].p==1)add(q[i].y,-q[i].z); for(int i=l;i<=r;i++){ if(q[i].t<=mid)tmp[ll++]=q[i]; else tmp[rr++]=q[i]; } for(int i=l;i<=r;i++)q[i]=tmp[i]; work(l,mid);work(mid+1,r); } int main(){ scanf("%d",&n); int f,x1,x2,y1,y2,z; while(1){ scanf("%d",&f); if(f==1){ scanf("%d%d%d",&x1,&y1,&z); q[++tot].x=x1,q[tot].y=y1,q[tot].p=1,q[tot].z=z,q[tot].t=tot; } if(f==2){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); q[++tot].x=x2,q[tot].y=y2,q[tot].p=2,q[tot].z=1,q[tot].t=tot,q[tot].b=++t; q[++tot].x=x2,q[tot].y=y1-1,q[tot].p=2,q[tot].z=-1,q[tot].t=tot,q[tot].b=t; q[++tot].x=x1-1,q[tot].y=y2,q[tot].p=2,q[tot].z=-1,q[tot].t=tot,q[tot].b=t; q[++tot].x=x1-1,q[tot].y=y1-1,q[tot].p=2,q[tot].z=1,q[tot].t=tot,q[tot].b=t; } if(f==3)break; } sort(q+1,q+tot+1,cmp); work(1,tot); for(int i=1;i<=t;i++){ //cout<<ans[i]<<endl; printf("%d\n",ans[i]);//不要用cout，蜜汁RE } }