被一个叫做旺仔的坏学长教会的算法---CDQ分治，和归并排序很像，只是在归并排序的过程中对每个查询进行统计。
下面这个是他的博客链接：
我主要结合hdu 5126这个题来讲解CDQ分治的具体做法：
题目链接：
题目大意：
在一个三维空间当中，每次进行一个操作，添加一个点或者统计空间中的某一个长方体范围内的所有点
题目分析：
就是用CDQ分治就离线的统计出每个查询的结果
首先我们将每个点z坐标离散化，那么我们就可以利用树状数组统计出每个查询点之前插入的点的z坐标小于等于当前查询的点的个数。
那么我们就是要先将x,y序不大于当前查询，且时序小于当前查询的点先加入的树状数组当中，
那么这一步操作我们需要进行一个嵌套的CDQ分治：
1.既然是分治，那么一定要先对区间进行划分，采用最常用的二分的方法进行划分，然后递归的进行划分
2.当分治到段的大小为1的时候开始在回溯的过程中进行归并
3.首先我们能够保证之前的每一段内的按照y坐标升序排序，且左半段的时序均小于右半段的时序，而且每段内部的查询针对于当前段内部的点已经统计过，那么对于左半段因为统计结果不会和比他时序大的查询点有关系，所以已经是当前段的最终结果，而右半段因为左半段的时序都比他小，所以只要是y坐标比他小的，就能会对右半段中的点的统计结果有影响。
4.那么我们就将左半段的数据点和右半段的查询点放入一个新的数组，在这个数组当中，能够保证y的升序，且数据点和查询点分别保证了时序的升序
5.那么我们对这个新构建的数组再做一次CDQ分治，也就是再对它进行划分，递归的划分
6.当新的数组划分为1的时候，进行归并，在归并的过程中，左半段的数据点时序一定小于右半段的查询点，且左半段的y坐标一定不大于右半段的查询点，那么我们就是在归并的过程按照x坐标进行，归并，左半段内部保证按照x坐标有序，右半段也是按照x坐标有序，所以说对于左半段的数据点要加入到树状数组当中，对于右半段中的查询点统计之前树状数组中插入的z坐标不大于当前查询点z坐标的全部的值。
7.然后继续归并，一致维护数组的性质即可，在这一过程中，在第二次CDQ分治中，因为数组中凡是存在于查询点之前的数据点均保证了y,时序均在查询点之前，所以在对x序进行归并的时候，右半部的查询点只要x坐标大于左半部的数据点就能够满足x,y时序均小于查询点，在加上树状数组的操作，就能统计出比当前查询点x,y,z时序均小的点的个数了
8.然后对于每个查询的切割，就是利用长方体，利用切补法转化为多个前缀和的查询，然后统计一下就好了
代码如下：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 450007
using namespace std;
//用来存储星星和每次查询拆分出的点的数据结构
struct Node
{
int x,y,z,p,t;
Node(){}
Node( int x , int y , int z , int p , int t )
:x(x),y(y),z(z),p(p),t(t){}
};
Node star[MAX];
Node star2[MAX];
Node star3[MAX];
int tree[MAX];
int lowbit ( int x )
{
return x&-x;
}
void add ( int i ,int x )
{
while ( i < MAX )
{
tree[i] += x;
i += lowbit(i);
}
}
int get ( int i )
{
int ans = 0;
while ( i )
{
ans += tree[i];
i -= lowbit ( i );
}
return ans;
}
int res[MAX];
//CDQ针对于y坐标上的分治
void CDQ2 ( int l , int r )
{
if ( l == r ) return;//当前分段情况下仅有一个元素时返回
int mid = (l+r)/2;//将当前处理的段进行分段
CDQ2( l , mid );//对前半段进行分治处理
CDQ2( mid+1 , r );//对后半段进行分治处理
//因为分治操作保证了前半段和后半段已经维护好，也就是前半段中的元素以y为关键字是有序的
//后半段的元素以y为关键字同样也是有序的
//所以我们可以采取类似于归并排序的方式将两个段归并，并进行处理
int l1 = l , r1 = mid+1;
while ( r1 <= r )
{
//左侧中所有的点的时序均小于右侧的，所以右侧的查询会包含左侧的y坐标比x坐标小的点
//将这些点加入到树状数组中，那么我们就可以查询到这些点中中z坐标比当前查询小的
while ( l1 <= mid && star2[l1].y <= star2[r1].y )
{
if ( star2[l1].t == 0 ) add ( star2[l1].z , 1 );
l1++;
}
//如果当前是一个查询，那么统计左侧有多少个在它查询范围内的点
if ( star2[r1].t != 0 )
{
res[star2[r1].p] += get ( star2[r1].z ) * star2[r1].t;
}
r1++;
}
//将树状数组还原
while ( l1 > l )
{
--l1;
if ( star2[l1].t == 0 ) add ( star2[l1].z , -1 );
}
l1 = l , r1 = mid+1;
//将两个段的元素归并，保持原有的性质
for ( int i = l ; i <= r ; i++ )
if ( (l1 <= mid && star2[l1].y <= star2[r1].y) || r1 > r )
star3[i] = star2[l1++];
else star3[i] = star2[r1++];
for ( int i = l ; i <= r ; i++ )
star2[i] = star3[i];
}
//CDQ针对于X坐标上的分治
void CDQ1 ( int l , int r )
{
if ( l == r ) return;
int mid = (l+r)/2;//将当前段分成两段
CDQ1(l,mid);//对第一段进行分治
CDQ1(mid+1,r);//对第二段进行分治
int l1 = l , r1 = mid+1 , n = 0;
while ( r1 <= r )
{
//左侧的查询在之前的分治过程中已经统计完毕，所以跳过
while ( star[l1].t != 0 && l1 <= mid ) l1++;
//右侧中的元素已经被右侧的查询已经被统计过，所以跳过
while ( star[r1].t == 0 && r1 <= r ) r1++;
if ( r1 > r ) break;
//构造出需要统计的star2数组，继续进行分治统计
if ( (star[l1].x <= star[r1].x && l1 <= mid ) || r1 > r )
star2[n++] = star[l1++];
else star2[n++] = star[r1++];
}
if ( n > 0 ) CDQ2(0,n-1);
l1 = l , r1 = mid+1;
//归并当前数组当中的结果
for ( int i = l ; i <= r ; i++ )
{
if ( (star[l1].x <= star[r1].x && l1 <= mid )|| r1 > r )
star3[i] = star[l1++];
else star3[i] = star[r1++];
}
for ( int i = l ; i <= r ; i++ )
star[i] = star3[i];
}
int compn ( Node a, Node b )
{
return a.p < b.p;
}
int compz ( Node a , Node b )
{
return a.z < b.z;
}
int main ( )
{
int t,q,a,x1,y1,z1,x2,y2,z2;
scanf ( "%d" , &t );
while ( t-- )
{
int n = 0;
scanf ( "%d" , &q );
while ( q-- )
{
scanf ( "%d" , &a );
if ( a == 1 )
{
scanf ( "%d%d%d" , &x1 , &y1 , &z1 );
star[n++] = Node ( x1 , y1 , z1 , n , 0 );
}
else
{
scanf ( "%d%d%d%d%d%d" , &x1 , &y1 , &z1 , &x2 , &y2 , &z2 );
star[n++] = Node ( x2 , y2 , z2 , n , 1 );
star[n++] = Node ( x2 , y1-1 , z2 , n , -1 );
star[n++] = Node ( x1-1 , y2 , z2 , n , -1 );
star[n++] = Node ( x2 , y2 , z1-1 , n , -1 );
star[n++] = Node ( x1-1 , y1-1 , z2 , n , 1 );
star[n++] = Node ( x1-1 , y2 , z1-1 , n , 1 );
star[n++] = Node ( x2 , y1-1 , z1-1 , n , 1 );
star[n++] = Node ( x1-1 , y1-1 , z1-1 , n , -1 );
}
}
memset ( res , 0 , sizeof ( res ));
sort ( star , star+n , compz );
a = 1;
star[n].z = -1;
for ( int i = 0 ; i < n ; i++ )
if ( star[i].z != star[i+1].z )
star[i].z = a++;
else star[i].z = a;
sort ( star , star+n , compn );
CDQ1(0,n-1);
sort ( star , star+n , compn );
for ( int i = 0 ; i < n ; i++ )
{
if ( star[i].t != 0 )
{
int ans = 0;
for ( int j = 0 ; j < 8 ; j++ )
ans += res[i+j];
printf ( "%d\n" , ans );
i += 7;
}
}
}
return 0;
}