首页 > 代码库 > bzoj2683
bzoj2683
2683: 简单题
Time Limit: 50 Sec Memory Limit: 128 MBSubmit: 1018 Solved: 413
[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。
双倍经验
看到了无聊交了一下。。。
#include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; const int N=2000010; struct data { int x,y,dir,pos,type,delta; }event[N]; int n,size,w,s,m,pos,opt; vector<data> c; int tree[N],ans[N]; bool cp(data x,data y) { if(x.x!=y.x) return x.x<y.x; if(x.y!=y.y) return x.y<y.y; return x.type<y.type; } int lowbit(int x) { return x&(-x); } void update(int pos,int delta) { for(int i=pos;i<=N+1;i+=lowbit(i)) { tree[i]+=delta; } } int sum(int pos) { int ret=0; for(int i=pos;i>0;i-=lowbit(i)) { ret+=tree[i]; } return ret; } void cdq(int l,int r) { if(l>=r) return; int mid=(l+r)/2; cdq(l,mid); cdq(mid+1,r); c.clear(); for(int i=l;i<=mid;i++) if(event[i].type==1) c.push_back(event[i]); for(int i=mid+1;i<=r;i++) if(event[i].type==2) c.push_back(event[i]); sort(c.begin(),c.end(),cp); for(int i=0;i<c.size();i++) { // printf("type=%d pos=%d\n",c[i].type,c[i].pos); if(c[i].type==1) update(c[i].y,c[i].delta); if(c[i].type==2) { ans[c[i].pos]+=sum(c[i].y)*c[i].dir; // printf("%d\n",sum(c[i].y)); } } for(int i=0;i<c.size();i++) if(c[i].type==1) update(c[i].y,-c[i].delta); } void addquery(int x,int y,int dir) { event[++m].x=x; event[m].y=y; event[m].dir=dir; event[m].pos=pos; event[m].type=2; } int main() { scanf("%d",&s); while(scanf("%d",&opt)) { if(opt==3) break; int x,y,delta,x1,y1,x2,y2; if(opt==1) { scanf("%d%d%d",&x,&y,&delta); x++; y++; m++; event[m].type=opt; event[m].x=x; event[m].y=y; event[m].delta=delta; } else if(opt==2) { ++pos; //ans[++pos]+=abs(x1-x2)*abs(y1-y2)*s; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++; x2++; y1++; y2++; addquery(x1-1,y1-1,1); addquery(x2,y2,1); addquery(x1-1,y2,-1); addquery(x2,y1-1,-1); } } cdq(1,m); for(int i=1;i<=pos;i++) { printf("%d\n",ans[i]); } return 0; }
bzoj2683
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。