CDQ分治

CDQ 分治是一种思想而不是具体的算法。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：

解决和点对有关的问题。
1D 动态规划的优化与转移。
通过 CDQ 分治，将一些动态问题转化为静态问题。

来自OIERDB。
介绍听的有点乱，是吧。实际上很简单，就是将需要分治的区间分为子区间，然后假设我们可以获得子区间的答案，呢么我们还需要算出这个区间里所有子区间之间相互影响的答案。层层递归，最终求解。

第一道例题

一个很经典的问题是三维偏序问题：即给你n个三元组，要求你求出对于每个三元组有多少个其他三元组严格不大于该三元组。
二位偏序我们一般解决的方式是使用树状数组来求，将权值离散化后按第一关键字顺序插入至树状数组里第二关键字所对应的位置，这样我们在计算的时候就可以直接用树状数组求和，来得出对于每个三元组有多少合适的三元组在它前面。
简单的剖析一下这个过程，因为插入的顺序是按第一关键字排序，所以保证了目前树状数组里的元素第一关键字严格不大于目前元素的第一关键字，插入树状数组第二关键字对应的位置保证了第二关键字的严格不降。
假如我们想要在树状数组的基础上求三维偏序，呢么第三关键字也需要保证严格不降。此时就用到了cdq分治。

用CDQ分治来解决

我们首先按照第一关键字排序，然后使用cdq分治将区间分为左右两个区间，此时严格不大于关系只有三种，一种是全在左区间，一种是全在右区间，一种是大的在右区间，不大的在左区间。
全在左右两子区间的我们可以递归解决，我们只需要解决不大的元素在左区间，大的元素在右区间这种规则下有多少种分法。
很明显，右区间的第一关键字绝对大于左区间的第一关键字，因此就算我们将左区间或右区间单独排序也不会改变第一关键字的关系。呢就将第二第三关键字按照二维偏序的方式算得即可。
由于我们可以先处理子区间，也就是可以保证子区间是有序的（按第二关键字排序），也就是使用类似归并排序的方式来搞。这样我们就可以直接按照顺序将第三关键字插入树状数组中得到结果。
具体实现见例题代码：
洛谷3810

代码

#include < bits/stdc++.h >
#define maxn 200010
using namespace std;
long long n,k,kl,C[maxn],A[maxn],nn[maxn];
struct ss
{
	long long a,b,c,num,id;
}e[maxn],B[maxn];
inline bool mycmp(ss a1,ss a2){
if(a1.a!=a2.a)return a1.a<a2.a;
else if(a1.b!=a2.b)return a1.b<a2.b;
return a1.c<a2.c;}
inline bool cmp(ss a1, ss a2){return a1.id<a2.id;}
inline void copy(int q1,int q2){B[q1].a=e[q2].a;B[q1].b=e[q2].b;B[q1].c=e[q2].c;B[q1].id=e[q2].id;B[q1].num=e[q2].num;}
inline int lowbit(int kk){return kk&(-kk);}
int add(int yu,int kk){for(int kl=yu;kl<=k;kl+=lowbit(kl))C[kl]+=kk;return 0;}
int Find(int kk){int sum=0;for(int kl=kk;kl>0;kl-=lowbit(kl))sum+=C[kl];return sum;}
inline void merge(int ll,int rr)
{
	if(ll+1==rr)
	{
		if(e[rr].b<e[ll].b)B[++kl]=e[rr],e[rr]=e[ll],e[ll]=B[kl];
		kl=0;return ;
	}
	int mid=(ll+rr)/2;kl=0;
	for(int i=ll,j=mid+1;kl<=(rr-ll+1);)
	{
		while(i==mid+1){if(j==rr+1)break;copy(++kl,j++);}
		while(j==rr+1){if(i==mid+1)break;copy(++kl,i++);}
		if(e[i].b<=e[j].b&&i<=mid){copy(++kl,i++);}
		else if(j<=rr){copy(++kl,j++);}
		else break;
	}//cout<<ll<<' '<<rr<<'-'<<kl<<endl;
	for(int i=1;i<=kl;i++)e[i+ll-1]=B[i];
	//cout<<ll<<'-'<<rr<<'='<<kl<<':';for(int i=1;i<=kl;i++)cout<<e[i+ll-1].b<<' ';cout<<endl;
	return ;
}
inline void slove(int ll,int rr)
{
	int mid=(ll+rr)/2,ans=0;
	for(int i=mid+1,j=ll;i<=rr;i++)
	{
		while(e[j].b<=e[i].b&&j<=mid)add(e[j].c,e[j].num),j++;
		A[e[i].id]+=Find(e[i].c);
	}
	//for(int i=1;i<=k;i++)cout<<C[i]<<' ';cout<<endl;
	for(int i=mid+1,j=ll;i<=rr;i++)while(e[j].b<=e[i].b&&j<=mid)add(e[j].c,(0-e[j].num)),j++;
}
inline int cdq(int ll,int rr)
{
	if(ll==rr)return 0;
	int mid=(ll+rr)/2,ans=0;
	ans+=cdq(ll,mid);
	ans+=cdq(mid+1,rr);
	slove(ll,rr);
	//cout<<ll<<' '<<rr<<'\n';
	//for(int i=1;i<=n;i++)cout<<A[e[i].id]<<' ';cout<<'\n';
	//for(int i=1;i<=n;i++)cout<<e[i].a<<' ';cout<<'\n';
	//for(int i=1;i<=n;i++)cout<<e[i].b<<' ';cout<<'\n';
	//for(int i=1;i<=n;i++)cout<<e[i].c<<' ';cout<<'\n';
	//for(int i=19;i<=n;i++)cout<<e[i].num<<' ';cout<<'\n';
	//for(int i=1;i<=n;i++)cout<<e[i].id<<' ';cout<<'\n';
	merge(ll,rr);
	return ans;
}
int main()
{
	memset(e,10,sizeof(e));
	scanf("%lld%lld",&n,&k);
	int yu=0;	
	for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&e[i].a,&e[i].b,&e[i].c),e[i].num=1,e[i].id=i;
	sort(e+1,e+n+1,mycmp);
	for(int i=1;i<=n;i++)
		if(e[i].a==e[i-1].a&&e[i].b==e[i-1].b&&e[i].c==e[i-1].c)
		{
			e[i].num+=e[i-1].num;
			e[i-1]=e[0];
			yu++;
		}
	sort(e+1,e+n+1,mycmp);
	n-=yu;
	cdq(1,n);
	//for(int i=1;i<=n;i++)cout<<A[e[i].id+e[i].num-1]<<' ';cout<<'\n';
	
	for(int i=1;i<=n;i++)nn[A[e[i].id]+e[i].num-1]+=e[i].num;
	n+=yu;
	for(int i=0;i<n;i++)printf("%lld\n",nn[i]);
	return 0;
}