简介

CDQ分治是分治的一种, 可以看做归并排序的扩展, 利用离线将一些 \(O(n)\) 的暴力优化到 \(O(log n)\).

它可以用来顶替一些高级(log)数据结构等.

一般地, CDQ分治分为三部分:

1. 递归左右区间
2. 统计左区间对右区间的贡献
3. 合并整个区间

或者:

1. 递归左右区间
2. 分别合并左, 右区间
3. 统计左区间对右区间的贡献

这两种方法一般来说是等价的.

详见代码.

代码

利用cdq分治求三维偏序.

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

using namespace std;

#define rep(i,l,r) for(register int i=(l);i<=(r);++i)

#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)

#define il inline

typedef double db;

typedef long long ll;

//---------------------------------------

const int nsz=1e5+5,ksz=2e5+5;

int n0,n=0,k,ans[nsz];

struct tl{int a,b,c,cnt,res;}line[nsz]{{-1,-1,-1,0,0}};

bool cmpa(tl a,tl b){return a.a!=b.a?a.a<b.a:a.b!=b.b?a.b<b.b:a.c<b.c;}

bool cmpb(tl a,tl b){return a.b!=b.b?a.b<b.b:a.c<b.c;}

bool eq(tl a,tl b){return a.a==b.a&&a.b==b.b&&a.c==b.c;}

//bit

int bit[ksz];

#define lb(p) ((p)&(-(p)))

void add(int p,int v){while(p<=k)bit[p]+=v,p+=lb(p);}

int qu(int p){

	int res=0;

	while(p)res+=bit[p],p-=lb(p);

	return res;

}

//第一种方式

tl l2[nsz];

void cdq(int l,int r){

	if(l==r)return;

	int mid=(l+r)>>1;

	cdq(l,mid);

	cdq(mid+1,r);

	int pl=l,pr=mid+1;

	rep(i,l,r){

		if(pl<=mid&&(pr==r+1||line[pl].b<=line[pr].b)) //important: <=

			add(line[pl].c,line[pl].cnt),l2[i]=line[pl++];

		else

			line[pr].res+=qu(line[pr].c),l2[i]=line[pr++];

	}

	rep(i,l,mid)add(line[i].c,-line[i].cnt);

	rep(i,l,r)line[i]=l2[i];

}

//第二种方式

void cdq1(int l,int r){

	if(l==r)return;

	int mid=(l+r)>>1;

	cdq1(l,mid);

	cdq1(mid+1,r);

	sort(line+l,line+mid+1,cmpb);

	sort(line+mid+1,line+r+1,cmpb);

	int p=l;

	rep(i,mid+1,r){

		while(line[p].b<=line[i].b&&p<=mid)add(line[p].c,line[p].cnt),++p;//important: <=

		line[i].res+=qu(line[i].c);

	}

	rep(i,l,p-1)add(line[i].c,-line[i].cnt);

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0);

	cin>>n0>>k;

	rep(i,1,n0)cin>>line[i].a>>line[i].b>>line[i].c;

	sort(line+1,line+n0+1,cmpa);

	rep(i,1,n0){

		if(!eq(line[i],line[n]))line[++n]=line[i];

		++line[n].cnt;

	}

	cdq(1,n);

//	rep(i,1,n)printf("%d %d %d %d %d\n",line[i].a,line[i].b,line[i].c,line[i].cnt,line[i].res);

	rep(i,1,n)ans[line[i].res+line[i].cnt-1]+=line[i].cnt;

	rep(i,0,n0-1)cout<<ans[i]<<'\n';

	return 0;

}