bzoj2683简单题 cdq分治

2683: 简单题

Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 1803 Solved: 731
[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分治三维偏序三维分别是操作序号，横坐标，纵坐标
把一个询问拆成4个，就变成了处理二维前缀和问题
对横坐标排序，操作序号cdq分治，纵坐标用bit处理

 #include<bits/stdc++.h>

 #define N 200005

 using namespace std;

 int n,m,t,c[N*],ans[N];

 struct query{

     int x,y,v,id,op,bl;

     bool operator < (const query &b)const{

         if(x==b.x&&y==b.y)return id<b.id;

         return x==b.x?y<b.y:x<b.x;

     }

 }q[N<<],a[N<<];

 void add(int x,int y,int v){

     if(!x||!y)return;

     q[++m].x=x;q[m].y=y;q[m].id=m;

     q[m].op=;q[m].bl=t;q[m].v=v;

 }

 void update(int p,int x){

     while(p<=n){

         c[p]+=x;

         p+=p&-p;

     }

 }

 int ask(int x){

     int ret=;

     while(x){

         ret+=c[x];

         x-=x&-x;

     }

     return ret;

 }

 void solve(int l,int r){

     if(l==r)return;

     int mid=(l+r)>>,p1=l,p2=mid+;

     for(int i=l;i<=r;++i){

         if(q[i].id<=mid&&q[i].op==)update(q[i].y,q[i].v);

         if(q[i].id>mid&&q[i].op==)ans[q[i].bl]+=ask(q[i].y)*q[i].v;

     }

     for(int i=l;i<=r;++i)

     if(q[i].op==&&q[i].id<=mid)update(q[i].y,-q[i].v);

     for(int i=l;i<=r;++i){

         if(q[i].id<=mid)a[p1++]=q[i];

         else a[p2++]=q[i];

     }

     for(int i=l;i<=r;++i)q[i]=a[i];

     solve(l,mid);solve(mid+,r);

 }

 int main(){

     scanf("%d",&n);

     while(){

         static int op,x1,x2,y1,y2,v;

         scanf("%d",&op);

         if(op==){

             scanf("%d%d%d",&x1,&y1,&v);

             q[++m].x=x1;q[m].y=y1;q[m].v=v;

             q[m].id=m;q[m].op=op;

         }

         if(op==){

             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);++t;

             add(x1-,y1-,);add(x2,y2,);

             add(x1-,y2,-);add(x2,y1-,-);

         }

         if(op==)break;

     }

     sort(q+,q++m);

     solve(,m);

     for(int i=;i<=t;i++)

     printf("%d\n",ans[i]);

     return ;

 }

CDQ分治