首页 > 代码库 > bzoj2683 简单题
bzoj2683 简单题
2683: 简单题
Time Limit: 50 Sec Memory Limit: 128 MBSubmit: 1282 Solved: 510
[Submit][Status][Discuss]
Description
你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：
命令 | 参数限制 | 内容 |
1 x y A | 1<=x,y<=N，A是正整数 | 将格子x,y里的数字加上A |
2 x1 y1 x2 y2 | 1<=x1<= x2<=N 1<=y1<= y2<=N | 输出x1 y1 x2 y2这个矩形内的数字和 |
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
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
3
5
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 }}
bzoj2683 简单题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。