COGS1752 [BOI2007]摩基亚Mokia（CDQ分治 + 二维前缀和 + 线段树）

题目这么说的：

摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户C的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。

在定位系统中，世界被认为是一个W×W的正方形区域，由1×1的方格组成。每个方格都有一个坐标(x,y)，1<=x,y<=W。坐标的编号从1开始。对于一个4×4的正方形，就有1<=x<=4,1<=y<=4（如图）：

请帮助Mokia公司编写一个程序来计算在某个矩形区域内有多少名用户。

有三种命令，意义如下：

0 W 初始化一个全零矩阵。本命令仅开始时出现一次。
1 x y A 向方格(x,y)中添加A个用户。A是正整数。
2 X1 Y1 X2 Y2 查询X1<=x<=X2，Y1<=y<=Y2所规定的矩形中的用户数量
3 无参数 结束程序。本命令仅结束时出现一次。

这篇题解写得挺详细的：http://wulala.logdown.com/posts/207262-boi-2007-mokia。

。。然后感觉这题转化成二维前缀和的差分挺厉害的。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 long long tree[<<];

 int N,x,y;

 void update(int i,int j,int k){

     if(i==j){

         tree[k]+=y;

         return;

     }

     int mid=i+j>>;

     if(x<=mid) update(i,mid,k<<);

     else update(mid+,j,k<<|);

     tree[k]=tree[k<<]+tree[k<<|];

 }

 long long query(int i,int j,int k){

     if(x>y) return ;

     if(x<=i && j<=y){

         return tree[k];

     }

     int mid=i+j>>;

     long long res=;

     if(x<=mid) res+=query(i,mid,k<<);

     if(y>mid) res+=query(mid+,j,k<<|);

     return res;

 }

 struct Query{

     int idx,type,anspos;

     int x,y,A;

     bool operator<(const Query &q) const {

         return x<q.x;

     }

 }que[],tmp[];

 long long ans[];

 void cdq(int l,int r){

     if(l>=r) return;

     int mid=l+r>>,i=l,j=mid+;

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

         if(que[k].idx<=mid) tmp[i++]=que[k];

         else tmp[j++]=que[k];

     }

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

         que[k]=tmp[k];

     }

     for(i=mid+,j=l; i<=r; ++i){

         if(que[i].type==) continue;

         for( ; j<=mid && que[j].x<=que[i].x; ++j){

             if(que[j].type==) continue;

             x=que[j].y; y=que[j].A;

             update(,N,);

         }

         x=; y=que[i].y;

         ans[que[i].anspos]+=query(,N,)*que[i].A;

     }

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

         if(que[i].type==) continue;

         x=que[i].y; y=-que[i].A;

         update(,N,);

     }

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

 }

 int main(){

     //freopen("mokia.in","r",stdin); freopen("mokia.out","w",stdout);

     int op,n,a,b,c,d;

     scanf("%d%d",&op,&n);

     int opn=,cnt=;

     while(scanf("%d",&op),op!=){

         if(op==){

             scanf("%d%d%d",&a,&b,&c);

             que[++opn].idx=opn; que[opn].type=; que[opn].x=a; que[opn].y=b; que[opn].A=c;

         }else if(op==){

             scanf("%d%d%d%d",&a,&b,&c,&d);

             ++cnt;

             que[++opn].idx=opn; que[opn].type=; que[opn].anspos=cnt; que[opn].x=c; que[opn].y=d; que[opn].A=;

             que[++opn].idx=opn; que[opn].type=; que[opn].anspos=cnt; que[opn].x=c; que[opn].y=b-; que[opn].A=-;

             que[++opn].idx=opn; que[opn].type=; que[opn].anspos=cnt; que[opn].x=a-; que[opn].y=d; que[opn].A=-;

             que[++opn].idx=opn; que[opn].type=; que[opn].anspos=cnt; que[opn].x=a-; que[opn].y=b-; que[opn].A=;

         }

     }

     for(N=; N<n; N<<=);

     sort(que+,que++opn);

     cdq(,opn);

     for(int i=; i<=cnt; ++i){

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

     }

     return ;

 }

COGS1752 [BOI2007]摩基亚Mokia（CDQ分治 + 二维前缀和 + 线段树）的相关教程结束。