2683: 简单题
Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 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=;
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+;i+=lowbit(i))
{
tree[i]+=delta;
}
}
int sum(int pos)
{
int ret=;
for(int i=pos;i>;i-=lowbit(i))
{
ret+=tree[i];
}
return ret;
} void cdq(int l,int r)
{
if(l>=r) return;
int mid=(l+r)/;
cdq(l,mid);
cdq(mid+,r);
c.clear();
for(int i=l;i<=mid;i++)
if(event[i].type==) c.push_back(event[i]);
for(int i=mid+;i<=r;i++)
if(event[i].type==) c.push_back(event[i]);
sort(c.begin(),c.end(),cp);
for(int i=;i<c.size();i++)
{
// printf("type=%d pos=%d\n",c[i].type,c[i].pos);
if(c[i].type==)
update(c[i].y,c[i].delta);
if(c[i].type==)
{
ans[c[i].pos]+=sum(c[i].y)*c[i].dir;
// printf("%d\n",sum(c[i].y));
}
}
for(int i=;i<c.size();i++)
if(c[i].type==) 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=;
} int main()
{
scanf("%d",&s);
while(scanf("%d",&opt))
{
if(opt==) break;
int x,y,delta,x1,y1,x2,y2;
if(opt==)
{
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==)
{
++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-,y1-,);
addquery(x2,y2,);
addquery(x1-,y2,-);
addquery(x2,y1-,-);
}
}
cdq(,m);
for(int i=;i<=pos;i++)
{
printf("%d\n",ans[i]);
}
return ;
}