POJ1195Mobile phones （从二维树状数组到cdq分治）

Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S * S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix.

Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area.

Input

The input is read from standard input as integers and the answers to the queries are written to standard output as integers. The input is encoded as follows. Each input comes on a separate line, and consists of one instruction integer and a number of parameter integers according to the following table.

The values will always be in range, so there is no need to check them. In particular, if A is negative, it can be assumed that it will not reduce the square value below zero. The indexing starts at 0, e.g. for a table of size 4 * 4, we have 0 <= X <= 3 and 0 <= Y <= 3.

Table size: 1 * 1 <= S * S <= 1024 * 1024
Cell value V at any time: 0 <= V <= 32767
Update amount: -32768 <= A <= 32767
No of instructions in input: 3 <= U <= 60002
Maximum number of phones in the whole table: M= 2^30

Output

Your program should not answer anything to lines with an instruction other than 2. If the instruction is 2, then your program is expected to answer the query by writing the answer as a single line containing a single integer to standard output.

Sample Input

Sample Output

3
4

题目：二维平面上单点加值操作，矩形区间求和操作。

显然这个数据可以用二维树状数组秒

//poj1195树状数组
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1100;
int sum[maxn][maxn],N;
int lowbit(int x) { return x&(-x); }
void add(int x,int y,int val)
{
    for(int i=x;i<=N;i+=lowbit(i))
     for(int j=y;j<=N;j+=lowbit(j))
      sum[i][j]+=val;
}
int query(int x,int y)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))
     for(int j=y;j;j-=lowbit(j))
      res+=sum[i][j];
    return res;
}
int main()
{
    int opt,a,b,x,y,val;
    while(~scanf("%d",&opt)){
        scanf("%d",&N);
        memset(sum,0,sizeof(sum));
        while(scanf("%d",&opt)){
            if(opt==3) break;
            if(opt==1){
                scanf("%d%d%d",&x,&y,&val);
                add(x+1,y+1,val);
            }
            else{
                scanf("%d%d%d%d",&x,&y,&a,&b);
                printf("%d
",query(a+1,b+1)+query(x,y)-query(a+1,y)-query(x,b+1));
            }
        }
    } return 0;
}

View Code

但如果操作不变，二维平面变大，空间不够时，cdq分治就来了。

首先看下面之前，先回顾一下上面的题，二维树状树组可以做，复杂度为（nlg2n），只是空间变大后不行。此题引用cdq分治是为了降二维树状数组为一维。（避免读者误以为cdq分治优化的是复杂度，其实复杂度没有降低。）

nmphy自诉：
  1，为了描述，这里假设分治[l,r]部分时，处理[l,mid]的增加对[mid+1,r]的影响叫做“合并”过程。
  2，以下的l，mid，r均是指第几个操作，即按时间排序后是第几个操作，而不是x坐标或者y坐标，不要搞混淆。
我们假设有q个操作（即按时间排序），现在在解决[l,r]这几个操作。
   可以肯定：当前合并过程中[mid+1，r]的增加的值全部来自于[l,mid]。
为什么呢？l之前增加的值对[mid+1,r]的影响呢呢？[mid+1,R]内部操作增加的值对内部后面的影响呢？
仔细一看，l之前增加的值在更大的分治里面(即[l,r]属于[L,R]，假设[L,R]=[L,mid]+[l,r]，那么l之前的[L,mid]部分就在这里合并处理)；
        而[mid+1,r]增加的值在更新的分治里（即[mid+1,(mid+1+r)/2],[(mid+2+r)/2+1,r]）。
从而保证了前面的增加对后面的询问都被考虑到。
但是[l,mid]对[mid+1,r]处理时，增加值使用了一次；合并后[l,r]对[r+1,r]处理时，显然[l,mid]的增加值又使用了一次。
所以在处理完内部后，还得减去增加值。

上面有点乱的话自己来问我，我觉得理解上面这段话还是很重要的！

所谓cdq分治，就是分治所有操作，计算[l,mid]中的修改对[mid+1,r]中的询问的影响。
无法理解的同学可以借助归并排序的思想思考。
抄袭别人讲以上的话吧
1、T(n)=2T(n/2)+O(kn)的解是T(n)=O(kn log n) 
2、T(n)=2T(n/2)+O(kn log n)的解是T(n)=O(kn log^2 n) 
3、T(n)=2T(n/2)+O(k)的解是T(n)=O(kn)

所以cdq分治的复杂度也可以简单的算出来了。
cdq能处理的题目必须满足：1、允许离线  2、前面的修改对后面的影响很容易算出来

比如说这一题
在[l,mid]部分的修改按x排序从小到大加进一个树状数组里，不断更新对[mid+1,r]的影响。
复杂度就是第二种计算方式，可就是O(q log^2 w)

因为我们从下向上扫描，所以不需要记录y轴方向的树状数组，只需要跟新x方向即可。

CDQ分治中，首先按x来排序，对t这个维度进行分治。
那么t<=mid的更新操作都能影响到t'>=mid+1的查询结果。
所以在CDQ(l,r)中，按照x从小到大扫一遍所有操作，遇到更新操作就在树状数组上插入y值（y值离散过），
遇到查询操作就给该操作的结果加上树状数组上查询到的sum(1,y)的值。
接下来用类似归并排序的方法，把t<=mid的操作都放到数组左半部分，t>=mid+1的操作都放到右半部分
这么做之后两半部分的y依然是有序的，就可以递归处理两半部分之间的更新操作对查询操作产生的影响了。

你瞅啥？

View Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
const int Maxn=200000;
int x1[Maxn],x2[Maxn],y1[Maxn],y2[Maxn],tr[Maxn];
int a[Maxn],b[Maxn],c[Maxn],opt[Maxn],ans[Maxn];
int n,m,s,w,i;
struct arr{
    int x,l,r,k,c;
    bool operator <(const arr &a) const { return x<a.x; }
}qk[Maxn];
struct ad{
    int x,y,w;
    bool operator <(const ad &a) const { return x<a.x; }
}g[Maxn];
int query(int x){
    int ret=0;
    for (int i=x;i>0;i-=lowbit(i)) ret+=tr[i];
    return ret;
}
void add(int x,int s){
    for(int i=x;i<=m;i+=lowbit(i)) tr[i]+=s;
}
void combine(int l,int r)
{
    int mid=(l+r)>>1,t=0,tt=0,i,j;
    for(i=mid+1;i<=r;i++)
       if(opt[i]==2){
          qk[++t]=(arr){x1[i]-1, y1[i], y2[i], i, 0};
          qk[++t]=(arr){x2[i],   y1[i], y2[i], i, 1};
    }
    sort(qk+1,qk+t+1); //按x排序
    for(i=l;i<=mid;i++)
      if(opt[i]==1) g[++tt]=(ad){x1[i],y1[i],x2[i]};
    sort(g+1,g+tt+1);
    for(i=1,j=1;i<=tt;i++){
       while(j<=t&&qk[j].x<g[i].x){
          if (qk[j].c==0)  ans[qk[j].k]-=query(qk[j].r)-query(qk[j].l-1);
          else ans[qk[j].k]+=query(qk[j].r)-query(qk[j].l-1);
          j++;
       } add(g[i].y,g[i].w);
    }
    while(j<=t){
       if(qk[j].c==0) ans[qk[j].k]-=query(qk[j].r)-query(qk[j].l-1);
       else ans[qk[j].k]+=query(qk[j].r)-query(qk[j].l-1);
       j++;
    }
    for(i=1;i<=tt;i++)  add(g[i].y,-g[i].w);//减去增加值
}
void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);  
    combine(l,r); //前+前半截对后半截的影响+后 
    cdq(mid+1,r);
}
int main(){
    scanf("%d%d",&s,&w); n=1;  //s是初始值，此题为0 
    while (true){
        scanf("%d",&opt[n]);
        if(opt[n]==0||opt[n]==3) break;
        if(opt[n]==1){
           scanf("%d%d%d",&x1[n],&y1[n],&x2[n]);
           c[++m]=y1[n];
        }else
        if(opt[n]==2){
           scanf("%d%d%d%d",&x1[n],&y1[n],&x2[n],&y2[n]);
           ans[n]+=s*(x2[n]-x1[n]+1)*(y2[n]-y1[n]+1);
           c[++m]=y1[n]; c[++m]=y2[n]; //c是复制y坐标来离散 
        }  n++;
    }
    sort(c+1,c+m+1);  //按y排序 
    m=unique(c+1,c+m+1)-(c+1);  //离散 
    for(i=1;i<n;i++){
        y1[i]=lower_bound(c+1,c+m+1,y1[i])-c;
        if(opt[i]==2) y2[i]=lower_bound(c+1,c+m+1,y2[i])-c;
    }   cdq(1,--n);
    for(i=1;i<=n;i++) if(opt[i]==2) printf("%d
",ans[i]);
    return 0;
}

园丁的烦恼 SHOI2007 BZOJ 1935

　　【模板】树状数组 1 luogu P3374

　　Mokia BZOJ 1176

　　陌上花开 BZOJ 3262

　　简单题BZOJ 2683

　　动态逆序对 CQOI2011 BZOJ 3295