之前听大神讲过CDQ分治大概是个什么东西，但是一直还没有真正去搞过。今天稍微看了一下，写点自己的理解。
首先CDQ分治有两个条件。
条件1：可以分成两个独立互不影响的问题（这里的“独立”是指将前面区间的影响处理掉后，后面与前面都成为了新的相同问题）
条件2：允许离线（据说最近流行强制在线。。。如果这样只好去写恶心的数据结构了）。
CDQ分治在可以使用的情况下很多高级数据结构题可以用CDQ分治干过去，不仅时空优越而且易于调试（虽然我并不觉得很好调试
大体思路是将问题不断分成两个子问题，用前一个子问题中的修改操作去更新后一个子问题，这样之后就得到了两个互不影响的子问题，达到分治的目的。
贴一道版题代码：BZOJ 1176
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-(x))
struct data{
int v,x,y,d,f,pos;
bool operator <(const data& w)const{
if(x!=w.x) return x<w.x;
if(y!=w.y) return y<w.y;
return pos<w.pos;
}
}a[],tmp[];
int s,w,t[],cnt,ans[];
int read(int& x){
x=; int f=,a=getchar();
while(a<'' || a>'') {if(a=='-') f=-; a=getchar();}
while(a>='' && a<='') x=x*+a-'',a=getchar(); x*=f;
}
inline void add(int y,int x){for(int i=y;i<=w;i+=lowbit(i)) t[i]+=x;}
inline int query(int y){int ret=; for(int i=y;i;i-=lowbit(i)) ret+=t[i]; return ret;}
void CDQ(int l,int r){
if(l==r) return;
int mid=(l+r)>>,t1=l-,t2=mid; //这里写错调了老半天
for(int i=l;i<=r;i++){
if(a[i].v<=mid && !a[i].pos) add(a[i].y,a[i].d);
if(a[i].v>mid && a[i].pos) ans[a[i].pos]+=query(a[i].y)*a[i].f;
}
for(int i=l;i<=r;i++)
if(a[i].v<=mid && !a[i].pos) add(a[i].y,-a[i].d);
for(int i=l;i<=r;i++)
if(a[i].v<=mid) tmp[++t1]=a[i];
else tmp[++t2]=a[i];
for(int i=l;i<=r;i++) a[i]=tmp[i];
CDQ(l,mid); CDQ(mid+,r);
}
int main(){
read(s); read(w); int t,x,y,d,x1,x2,y1,y2;
while(){
read(t);
if(t==){
read(x); read(y); read(d);
a[++cnt]=(data){cnt,x,y,d,,};
}else if(t==){
read(x1); read(y1); read(x2); read(y2); ++ans[];
a[++cnt]=(data){cnt,x1-,y1-,,,ans[]};
a[++cnt]=(data){cnt,x2,y2,,,ans[]};
a[++cnt]=(data){cnt,x1-,y2,,-,ans[]};
a[++cnt]=(data){cnt,x2,y1-,,-,ans[]};
}else break;
}
sort(a+,a++cnt);
CDQ(,cnt);
for(int i=;i<=ans[];i++)
printf("%d\n",ans[i]);
return ;
}