BZOJ 1176[Balkan2007]Mokia(CDQ分治）

1176: [Balkan2007]Mokia

Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 3381 Solved: 1520
[Submit][Status][Discuss]

Description

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):

"1 x y a"

"2 x1 y1 x2 y2"

"3"

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束

Output

对于每个输入2,输出一行,即输入2的答案

Sample Input

0 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

题解

首先这个s是假的，把它忽视掉。

天啊，昨天打CDQ分治打得太嗨了，就忘了更新博客了。

说真的，CDQ分治是真的好打，基本上除了开始几道都是1A

这题是个三维偏序裸题。。。

第一维排序，然后第二维CDQ分治，然后以第三维造树状数组。。。

具体看代码。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cmath>
  5 #include<algorithm>
  6 using namespace std;
  7 const int N=3000100;
  8 int s,n,tr[N],cnt,tot,ans[N];
  9 struct query{
 10     int id,k,w,x,y;
 11     bool operator <(const query &a)const{
 12         if(a.id==id){
 13             if(a.x==x){
 14                 if(a.y==y){
 15                     return a.k>k;
 16                 }
 17                 else return a.y>y;
 18             }
 19             else return a.x>x;
 20         }
 21         else return a.id>id;
 22     }
 23 }q[N],c[N];
 24 bool pd(query a,query b){
 25     if(a.x==b.x){
 26         if(a.y==b.y){
 27             return a.k<b.k;
 28         }
 29         else return a.y<b.y;
 30     }
 31     else return a.x<b.x;
 32 }
 33 int lowbit(int x){
 34     return x&-x;
 35 }
 36 void add(int x,int w){
 37     for(int i=x;i<=n;i+=lowbit(i)){
 38         tr[i]+=w;
 39     }
 40 }
 41 int getsum(int x){
 42     int ans=0;
 43     for(int i=x;i>=1;i-=lowbit(i)){
 44         ans+=tr[i];
 45     }
 46     return ans;
 47 }
 48 void cdq(int l,int r){
 49     if(l==r)return;
 50     int mid=(l+r)>>1;
 51     cdq(l,mid);cdq(mid+1,r);
 52     int ll=l;int rl=mid+1;int now=0;
 53     while(ll<=mid&&rl<=r){
 54         if(pd(q[ll],q[rl])){
 55             if(q[ll].k==1)add(q[ll].y,q[ll].w);
 56             c[++now]=q[ll++];
 57         }
 58         else{
 59             if(q[rl].k==2)ans[q[rl].w]-=getsum(q[rl].y);
 60             else if(q[rl].k==3)ans[q[rl].w]+=getsum(q[rl].y);
 61             c[++now]=q[rl++];
 62         }
 63     }
 64     while(ll<=mid){
 65         if(q[ll].k==1)add(q[ll].y,q[ll].w);
 66         c[++now]=q[ll++];
 67     }
 68     while(rl<=r){
 69         if(q[rl].k==2)ans[q[rl].w]-=getsum(q[rl].y);
 70         else if(q[rl].k==3)ans[q[rl].w]+=getsum(q[rl].y);
 71         c[++now]=q[rl++];
 72     }
 73     for(int i=l;i<=mid;i++){
 74         if(q[i].k==1)add(q[i].y,-q[i].w);
 75     }
 76     for(int i=l;i<=r;i++){
 77         q[i]=c[i-l+1];
 78     }
 79 }
 80 int main(){
 81     scanf("%d%d",&s,&n);
 82     n+=2;
 83     while(1){
 84         int k;
 85         scanf("%d",&k);
 86         if(k==1){
 87             int x,y,a;
 88             scanf("%d%d%d",&x,&y,&a);
 89             x+=2;y+=2;
 90             q[++cnt].x=x;q[cnt].y=y;
 91             q[cnt].id=cnt;q[cnt].k=1;
 92             q[cnt].w=a;
 93         }
 94         else if(k==2){
 95             int x1,y1,x2,y2;
 96             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
 97             x1+=2;y1+=2;x2+=2;y2+=2;
 98             q[++cnt].x=x2;q[cnt].y=y2;q[cnt].id=cnt;q[cnt].k=3;q[cnt].w=++tot;
 99             q[++cnt].x=x1-1;q[cnt].y=y2;q[cnt].id=cnt;q[cnt].k=2;q[cnt].w=tot;
100             q[++cnt].x=x2;q[cnt].y=y1-1;q[cnt].id=cnt;q[cnt].k=2;q[cnt].w=tot;
101             q[++cnt].x=x1-1;q[cnt].y=y1-1;q[cnt].id=cnt;q[cnt].k=3;q[cnt].w=tot;
102         }
103         else break;
104     }
105     sort(q+1,q+1+cnt);
106 //    for(int i=1;i<=cnt;i++){
107 //        cout<<q[i].id<<" "<<q[i].x<<" "<<q[i].y<<" "<<q[i].k<<" "<<q[i].w<<endl;;
108 //    }
109     cdq(1,cnt);
110     for(int i=1;i<=tot;i++){
111         printf("%d
",ans[i]);
112     }
113     return 0;
114 }