学习了许多网上的博客后，发现大家都将CDQ和整体二分总结了在一起，可能两者之间真的有一些关联吧（尽管我没感觉到，反应迟钝。。。）所以我还是决定学习了这两个后再来做一个小小的总结（当然学艺不精，欢迎大家指出错误，因为本来就是一点个人复习）
【CDQ分治】
由IOI大佬 陈丹琦发明 %%%一波大佬（女选手都这么强，还有什么理由不好好学OI）
CDQ的思路大致如下：
对于一个区间（l , r）
1、将区间拆分成（l,mid）和（mid+1,r）两个区间
2、因为左区间于右区间是结构相同的，所以递归处理两个区间
3、考虑处理左区间对右区间的贡献
那么CDQ可以干什么呢？？？
【处理三位偏序】
我们来看一道题：陌上花开
【思路分析】
看到这道题后会很容易想到逆序对，没错如果是二维偏序的话我们当然可以使用归并排序或树状数组来找（只需要将第一维排序一下，然后对第二维做逆序对）
如今我们有了三维，我们定义第一，二，三维为a,b,c。首先我们还是先将第一维排好序，然后我们发现我们就只需要对两维再进行讨论了。
然后我们就需要对其进行CDQ了，首先当我们处理到了一个区间时，我们将其二分为左区间和右区间，显然我们要先处理左区间，然后算出其对右区间的贡献（这里的贡献就是有多少满足bl<br&&cl<cr）。
那么我们怎么计算左区间对右区间的贡献呢？？？这里就是CDQ的关键了：
我们要对左区间，右区间分别排序使其的b分别有序，我们这时就进行对比，设立两个指针左区间 i ,右区间 j。如果bi<bj，那么 j 之后的b一定都大于bi，所以我们就把这个j号点丢进树状数组。如果不理解的话，我们这里可以想象成一个二维平面：
对于每个节点我们要找的就是在其左下方的节点个数，然后由于我们已经把b排好序了，所以我们只需要找c小的，所以我们对于c这一维建立一个值域树状数组，然后就可以很轻松地求出比其c小的节点个数了（如7号点就有6个点满足，又如5号点有一个满足）
1 void CDQ(int l,int r) 2 { 3 if(l==r) return; 4 int mid=(l+r)/2; 5 CDQ(l,mid),CDQ(mid+1,r);//首先处理好左右两区间，再进行区间信息合并 6 sort(t+l,t+mid+1,CMP);sort(t+mid+1,t+r+1,CMP);//先保证左右区间都是有序的 7 int i=l,j=mid+1; 8 for(;j<=r;j++) 9 { 10 while(t[i].b<=t[j].b&&i<=mid)//如果满足情况的话那就丢进树状数组 11 add(t[i].c,t[i].num),i++; 12 t[j].ans+=ask(t[j].c);//接着我们就要统计b,c都比小的，那么之前左区间满足的还在树状数组里，然后就成功统计 13 } 14 for(int j=l;j<i;j++) 15 add(t[j].c,-t[j].num);//每次处理完一个区间要把树状数组清空，但我们不要全清完，我们只需要把改过的点清空就好 16 }
【代码实现】
1 #include<cstdio> 2 #include<algorithm> 3 #define lowbit(x) x&(-x) 4 using namespace std; 5 const int maxn=1e6+5; 6 struct sd{ 7 int a,b,c,num,ans; 8 }t[maxn],que[maxn]; 9 int n,k,cnt,tree[maxn],ans[maxn]; 10 bool judge(sd x,sd y) {return x.a==y.a&&x.b==y.b&&x.c==y.c;} 11 void add(int v,int ww) {while(v<=k) tree[v]+=ww,v+=lowbit(v);} 12 int ask(int v) {int sum=0;while(v) sum+=tree[v],v-=lowbit(v);return sum;} 13 bool cmp(sd x,sd y) 14 { 15 if(x.a!=y.a) return x.a<y.a; 16 if(x.b!=y.b) return x.b<y.b; 17 return x.c<y.c; 18 } 19 bool CMP(sd x,sd y) 20 { 21 if(x.b!=y.b) return x.b<y.b; 22 return x.c<y.c; 23 } 24 void CDQ(int l,int r) 25 { 26 if(l==r) return; 27 int mid=(l+r)/2; 28 CDQ(l,mid),CDQ(mid+1,r); 29 sort(t+l,t+mid+1,CMP);sort(t+mid+1,t+r+1,CMP); 30 int i=l,j=mid+1; 31 for(;j<=r;j++) 32 { 33 while(t[i].b<=t[j].b&&i<=mid) 34 add(t[i].c,t[i].num),i++; 35 t[j].ans+=ask(t[j].c); 36 } 37 for(int j=l;j<i;j++) 38 add(t[j].c,-t[j].num); 39 } 40 int main() 41 { 42 scanf("%d%d",&n,&k); 43 for(int i=1;i<=n;i++) 44 scanf("%d%d%d",&que[i].a,&que[i].b,&que[i].c); 45 sort(que+1,que+1+n,cmp); 46 for(int i=1;i<=n;i++) 47 if(!judge(que[i],que[i-1])) t[++cnt]=que[i],t[cnt].num=1; 48 else t[cnt].num++; 49 CDQ(1,cnt); 50 for(int i=1;i<=cnt;i++) 51 ans[t[i].ans+t[i].num-1]+=t[i].num; 52 for(int i=0;i<n;i++) 53 printf("%d ",ans[i]); 54 return 0; 55 }
【整体二分】
由不知名的某OI大佬发明，还是%%%一波大佬（不知名的大佬都能这么厉害，还有什么理由不好好学OI）
首先我们来看一道题：k大数查询
对于这道题我们发现是求第k大，就是排名为n-k的数，很显然不太符合一般的逻辑（当然如果你的逻辑就这样那就很妙妙了。。。），那么我们可以取反（就是把每个数记为值域上限减这个数a=max-a，这样也不会有负数）
整体二分个人理解就是对值域和操作一起二分。
来看看这种题的一般套路：
f(二分下界l， 二分上界r， 队首， 队尾){ if(队列空) return; if(l == r) 队列内的所有询问答案为l, return ; int mid = 上下界中值; 清空线段树/树状数组。 扫描队列： 若是修改操作，if 修改值<=mid 丢到队列1; else 修改区间 丢到队列2; 若是询问操作，if 询问答案+当前贡献 < 所需答案k 更新询问答案，丢入队列1; else 丢入队列2; f(l, mid, 队列1); f(mid+1, r, 队列2); } **还原(线段树/树状数组)的复杂度不能与序列长度线性相关，否则会退化。只能与当前队列长度相关。
未完待续。。。（待填坑）