简介

cdq 分治常用于计算序列中需要满足某些限制的点对对答案的贡献，通常点对有 \(O(n^2)\) 个。

核心思想

与普通分治类似，把点对分成前半个区间和后半个区间的点对，但 cdq 分治还要处理跨越区间中点的点对，这就是 cdq 分治的核心所在。

算法流程

下面以三维偏序为例。 P3810 【模板】三维偏序（陌上花开）

首先把元素相同的合并，因为 cdq 分治一般解决不了有重复元素的问题，除非重复元素之间不算贡献。

与二维偏序类似，我们把所有元素按 \(a_i,b_i,c_i\) 分别为第一、二、三关键字排序，可以去除一维，变成带顺序限制的二维偏序问题。

此时右区间的每一个点显然都不会对左区间的点产生贡献，那么对左右区间分别按 \(a_i,b_i,c_i\) 为第一、第二关键字排序。观察到此时对于右区间的每一个 \(i\)，符合限制 \(b_j \leq b_i\) 的 \(j\) 一定是左区间的一段随着 \(i\) 增大单调不降的前缀。对于这个前缀查询，用一个 BIT 维护即可。

视值域与序列长度同阶，复杂度为 \(O(n \log^2 n)\).

注意重复元素也有贡献。

struct node {
	int a,b,c,cnt,ans,id;
}G[N];

BIT T; 

void solve(int l,int r) {
	if(l>=r) return;
	int mid=(l+r)>>1,le=l;
	solve(l,mid);solve(mid+1,r); // 分治计算不跨越中点的点对贡献 
	std::sort(e+l,e+mid+1,[](node a,node b) {return a.b==b.b?a.c<b.c:a.b<b.b;}); // 注意排序的地址位置 
	std::sort(e+mid+1,e+r+1,[](node a,node b) {return a.b==b.b?a.c<b.c:a.b<b.b;});
	for(int i=mid+1;i<=r;i++) { // 双指针统计答案 其中 i 指向右区间 le 指向左区间 
		while(le<=mid && e[le].b<=e[i].b) {T.modify(e[le].c,e[le].cnt);le++;}
		e[i].ans+=T.query(e[i].c);
	}
	for(int i=l;i<le;i++) T.modify(e[i].c,-e[i].cnt); // 清空 BIT 
}

int main() {
	// do something... 
	std::sort(G+1,G+1+n,[](node a,node b) {return a.a==b.a?(a.b==b.b?a.c<b.c:a.b<b.b):a.a<b.a;});
	for(int i=1;i<=n;i++) { // 合并相同元素 
		if(G[i].a!=G[i-1].a || G[i].b!=G[i-1].b || G[i].c!=G[i-1].c) e[++m]=G[i];
		++e[m].cnt;e[m].id=m;
	}
	solve(1,m);
	// do something... 
	return 0;
} 

注意每次分治/排序的时候对边界的计算。

结语

排序的地址有被恶心到一开始调了好久，以后注意。

感觉对分治的理解又加深了，其实以前一直不怎么懂分治。

参考文章

[1] 分治专题 https://www.cnblogs.com/alex-wei/p/divide_and_conquer.html