首页 > 代码库 > 简单题(bzoj 1683)
简单题(bzoj 1683)
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分治,先看了2013年集训队作业中许昊然的论文,有了一点初步理解,然后又做这个题, 感觉对cdq分治的大概思路有了一定认识。 cdq分治要求可离线,并且各个修改操作之间互不影响,且对查询操作的贡献独立。 我们考虑将操作分治,那么后一般操作中的修改是独立的,查询至于前一半的所有修改和后一般在它时间之前的修改有关, 对于前一半修改可以预处理,对于后一半在它之前的,可以递归处理。 这个题目的数据范围二维数据结构是不好过的,所以可以考虑将某一维排序,然后用一位数据结构维护。 我们用前缀和的思想,将求和操作理解为四个单点查询操作,然后对于每个查询操作x,y,对他有贡献的修改操作 一定是时间在它之前的并且x比它小的,所以我们可以按照x坐标排序,然后用树状数组维护y坐标的值。 */ #include<cstdio> #include<iostream> #include<algorithm> #define N 800010 using namespace std; int n,tot,T,ans[N],tree[N]; struct node{ int op,x,y,A,no,belong; };node Q[N],tq[N]; bool cmp(const node&s1,const node&s2){ if(s1.x==s2.x&&s1.y==s2.y) return s1.op<s2.op; if(s1.x==s2.x) return s1.y<s2.y; return s1.x<s2.x; } void modify(int x,int v){ while(x<=n){ tree[x]+=v; x+=x&(-x); } } int query(int x){ int sum=0; while(x){ sum+=tree[x]; x-=x&(-x); } return sum; } void solve(int l,int r){ if(l==r)return; int mid=l+r>>1; for(int i=l;i<=r;i++) if(Q[i].no<=mid&&Q[i].op==1) modify(Q[i].y,Q[i].A); else if(Q[i].no>mid&&Q[i].op==2){ if(Q[i].A) ans[Q[i].belong]+=query(Q[i].y); else ans[Q[i].belong]-=query(Q[i].y); } for(int i=l;i<=r;i++) if(Q[i].no<=mid&&Q[i].op==1) modify(Q[i].y,-Q[i].A); int l1=l,l2=mid+1; for(int i=l;i<=r;i++) if(Q[i].no<=mid)tq[l1++]=Q[i]; else tq[l2++]=Q[i]; for(int i=l;i<=r;i++) Q[i]=tq[i]; solve(l,mid);solve(mid+1,r); } int main(){ scanf("%d",&n); int opt,x,y,v,x1,y1; while(1){ scanf("%d",&opt); if(opt==1){ scanf("%d%d%d",&x,&y,&v); Q[++tot].op=1;Q[tot].x=x;Q[tot].y=y;Q[tot].A=v;Q[tot].no=tot; } else if(opt==2){ scanf("%d%d%d%d",&x,&y,&x1,&y1); Q[++tot].op=2;Q[tot].x=x-1;Q[tot].y=y-1;Q[tot].A=1;Q[tot].no=tot;Q[tot].belong=++T; Q[++tot].op=2;Q[tot].x=x-1;Q[tot].y=y1;Q[tot].A=0;Q[tot].no=tot;Q[tot].belong=T; Q[++tot].op=2;Q[tot].x=x1;Q[tot].y=y-1;Q[tot].A=0;Q[tot].no=tot;Q[tot].belong=T; Q[++tot].op=2;Q[tot].x=x1;Q[tot].y=y1;Q[tot].A=1;Q[tot].no=tot;Q[tot].belong=T; } else break; } sort(Q+1,Q+tot+1,cmp); solve(1,tot); for(int i=1;i<=T;i++) printf("%d\n",ans[i]); return 0; }
简单题(bzoj 1683)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。