CDQ 分治

CDQ 分治是一种离线分治算法。

前言/闲话

在考虑三维偏序进行CDQ分治时每一维用什么处理时，一般会把较难的用sort和树状数组解决，剩下的一维再用归并排序；

其实可以乱试，也就 $A_3^3$ 种情况而已，不多不多...

写博客时：

啊啊啊，写的好烦啊，实在不想看或赶时间，就看代码+画图+感性理解+细致分析讨论算了...

• 重点是要找出题目性质可以使用CDQ分治。

• CDQ分治很多种变式的，不要硬套模板，应该随机应变。

---

引入介绍

CDQ分治是用于解决多维偏序的问题，基于分治思想，可以潜意识理解为归并排序优化，一般上常见的有二维偏序和三维偏序。

怎么理解偏序呢，我的理解是：做一些题就知道了。

---

二维偏序

我们很早时候接触的逆序对个数问题其实就是二维偏序，满足一组 $(i,j)$ 是逆序对的条件是 $i<j$ 且 $a_i>a_j$，我们都知道可以用树状数组（线段树）和归并排序两种方法维护 $a_i$ 解决问题。

树状数组求逆序对比较常用，这里展示的是归并排序算法（有助于理解三维偏序）：

在归并的时候，对于区间 $[l,r]$，去把其分成两段，分别是左区间 $[l,mid]$ 和右区间 $[mid+1,r]$，对于答案的贡献，可以分为三类：

• 1.左区间 $[l,mid]$ 内部的贡献，这里可以直接向下递归；

• 2.同理，对于右区间 $[mid+1,r]$ 内部的贡献，也可以直接向下递归；

• 3.重点：左区间 $[l,mid]$ 和右区间 $[mid+1,r]$ 交叉形成的贡献。

由于左区间 $[l,mid]$ 和右区间 $[mid+1,r]$ 都是已经回溯的，规定这两个区间内的数肯定满足 $a_l<a_{l+1}<\cdots <a_{mid}$ 和 $a_{mid+1}<a_{mid+2}<\cdots <a_r$ 这一性质的；

（注：处理这个部分既可以归并时sort，也可以一边计算贡献一边排序，区别是第一种方法简单易懂，用途广，但时间复杂度会多一个log级；另一种呢，速度较上一种快，但归并时思考量大一些，且有些特殊的三位偏序无法解决。）

且这里左右贡献都已经计算了，所以我们只用关心右区间内的数原本的下标 $j$ 是否还是大于左区间里的数的下标 $i$，很显然，这是必定满足的，因为左右区间无论怎么排序，它里面的数的下标从一开始都已经是小于右区间的！这个性质很好的消掉了一维！妙啊！

两维条件中 $i<j$ 这一维是天然形成的，不需要额外进行排序，由上述，这一维会被巧妙的消掉；

接着考虑满足 $a_i>a_j$ 这一维，在归并 $[l,r]$ 顺带 计算贡献，这里的左区间和右区间的 $a_i$ 都已经是满足不下降的，指针 $i$ 和 $j$ 一开始分别指向 $l$ 和 $mid+1$；

当 $a_i\le a_j$ 时，进行普通归并；

当 $a_i>a_j$ 时，由性质可知区间 $[i,mid+1]$ 中的所有下标 $x$ 必定都满足 $a_x>a_j$，所以 $j$ 产生逆序对的个数贡献为 $mid-i+1$，反复如此，直到 $i=mid$ 或 $j=r$ 为止；

最后还需考虑多出来的 $i$ 或 $j$ 是否也要计算贡献（不能忽略，很有必要）...

时间复杂度是 $O(nlogn)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,a[N],tem[N],ans;
inline void MergeSort(int l,int r) {
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	MergeSort(l,mid);
	MergeSort(mid+1,r);
	int i=l,j=mid+1,k=0;
	while(i<=mid&&j<=r) {
		if(a[i]<=a[j])
			tem[++k]=a[i++];
		else {
			tem[++k]=a[j++]; 
			ans+=mid-i+1;
		}
	}
	while(i<=mid) tem[++k]=a[i++];
	while(j<=r) tem[++k]=a[j++]; 
	for(int i=l,j=1;i<=r;i++) 
		a[i]=tem[j++];
	return ;
}
signed main() {
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	MergeSort(1,n);
	printf("%lld\n",ans);
	return 0;
}

---

CF1311F Moving Points

Solution

分类讨论题，画个坐标轴，考虑两个维数：位置大小 $x_i$ 和速度大小 $v_i$；

先默认 $x_i<x_j$，对 $i,j$ 的速度按正负分类讨论，再分追及问题和相遇问题，可以得出以下结论：

同向移动时，若 $v_i>v_j$，$i$ 就一定能追到 $j$，贡献为 $0$，不用计算；否则无论如何都追不到，即 $v_i\le v_j$，贡献为初始位置的差 $x_j-x_i$；

异向移动时，若 $v_i\ge 0,v_j<0$（或 $v_i>0,v_j\le 0$），相向而行，必定相遇，贡献为 $0$；否则 $v_i\le 0,v_j\ge 0$，异向而行，永远不能相遇，贡献为 $x_j-x_i$，同样的这里大小关系也是 $v_i\le v_j$。

整理一下，这就是个二维偏序：

• ① $x_i<x_j$
• ② $v_i\le v_j$

套板子就可以了，注意第一维用sort处理掉。

---

三维偏序

【模板】三维偏序（陌上花开）

Solution

很明显给出了三维：

对于一组 $(i,j)$，需满足 $a_j\le a_i$ 且 $b_j\le b_i$ 且 $c_j\le c_i$ 且 $j\ne i$。

按上面说的，先用sort消掉第一维 $a_j\le a_i$，接下来考虑归并中的左右区间交叉贡献，同样，先让指针 $i$ 和 $j$ 一开始分别指向 $l$ 和 $mid+1$，归并第二维 $b_i\le b_j$；

这时候考虑如何解决第三维，尝试用 $log$ 级别的树状数组，由于是左区间对右区间贡献，所以当 $b_i\le b_j$ 时将 $c_i$ 加入树状数组中；当 $b_i>b_j$ 时，说明区间 $[l,i)$ 中所有的 $x$ 都满足 $a_x\le x_j$ 且 $b_x\le b_j$，那么只用在当前已有的树状数组中 $logV$ 去查找 $c_x\le c_j$ 的个数，并加入贡献即可。

小坑点：注意要去重（也不是完全意义上的去重），为什么呢？

可能有三维都完全相同的元素，本来这些元素相互之间都有贡献，可是在CDQ分治的过程中只有左区间贡献右区间；

就是说对于 $i$ 位置上的元素，假设有一个三个维数都和其一样的元素位与 $j$ 且 $j>i$，其实 $j$ 也对 $i$ 有贡献，但是却不会计算到，导致漏算，举个例子（$4$ 个数的 $a,b,c$）：

1 2 3，2 5 6，2 5 6，7 8 9

在归并时，第二个元素会对第三个元素产生 $1$ 点贡献，但是第三个元素不会在过程中给予第二个元素贡献，但是按题意，第三个元素也是要算入第二个元素中的；

为了解决这个问题，我们需要在一开始就把序列去重，并用 $cn{t}_i$ 记录 $i$ 元素出现的次数；CDQ分治在归并时，向树状数组中 $c_i$ 位置就要加上 $cn{t}_i$ 而不是 $1$；最后统计答案时，也要算上相同元素内部的贡献，也就是 $cn{t}_i-1$ 个。

普遍三维偏序的CDQ分治就是归并排序中加了个树状数组，一般为时间复杂度可以看作 $O(nlo{g}^{2}n)$，也可以这样计算 $O(nlognlogV)$，其中 $logV$ 属于树状数组；本题则是 $O(nlognlogk)$。

总结

小结一下做CDQ分治的思考步骤：

-- 待更新

【模板】Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int M=2e5+10;
int n,m,k;
struct Node {
	int x,y,z;
	int s,cnt;
} a[N],tem[N];
int sum[M],ans[N];
inline bool cmp(Node x,Node y) {
	if(x.x!=y.x)
		return x.x<y.x;
	if(x.y!=y.y)
		return x.y<y.y;
	return x.z<y.z;
}
inline int lowbit(int x) {
	return x&(-x); 
} 
inline void add(int x,int v) {
	while(x<=k) {
		sum[x]+=v;
		x+=lowbit(x);
	}
	return ;
}
inline int query(int x) {
	int Sum=0;
	while(x) {
		Sum+=sum[x];
		x-=lowbit(x);
	}
	return Sum;
}
inline void cdq(int ls,int rs) {
	if(ls>=rs)
		return ;
	int mid=(ls+rs)>>1;
	cdq(ls,mid);
	cdq(mid+1,rs);
	int cur=0,i=ls,j=mid+1;
	while(i<=mid&&j<=rs) {
		if(a[i].y<=a[j].y) {
			add(a[i].z,a[i].s);
			tem[++cur]=a[i++];
		} else {
			a[j].cnt+=query(a[j].z);
			tem[++cur]=a[j++];
		}
	}
	while(i<=mid) {
		add(a[i].z,a[i].s);
		tem[++cur]=a[i++];
	}
	while(j<=rs) {
		a[j].cnt+=query(a[j].z);
		tem[++cur]=a[j++];
	}
	for(int i=ls;i<=mid;i++)
		add(a[i].z,-a[i].s);
	for(int i=ls,j=1;j<=cur;i++,j++)
		a[i]=tem[j];
	return ;
}
inline bool equal(Node x,Node y) {
	if(x.x==y.x&&x.y==y.y&&x.z==y.z)
		return true;
	return false;
}
signed main() {
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
		a[i].s=1;
	}
	sort(a+1,a+n+1,cmp);
	m=1;
	for(int i=2;i<=n;i++) {
		if(equal(a[m],a[i])) {
			a[m].s++;
			continue;
		}
		a[++m]=a[i];
	}
	cdq(1,m);
	for(int i=1;i<=m;i++)
		ans[a[i].cnt+a[i].s-1]+=a[i].s;
	for(int i=0;i<n;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

---

四维偏序

不想讲了，就是多套一维，CDQ套CDQ套树状数组...

题目：P3157 [CQOI2011] 动态逆序对

---