偏序问题与 CDQ 分治

什么是偏序和拟序？

偏序关系：
设 $R$ 是集合 $A$ 上的一个二元关系，若 $R$ 满足：

自反性：对任意 $x∈A$ ，有 $x\ R\ x$ ；
反对称性（即反对称关系）：对任意 $x,y\in A$ ，若 $x\ R\ y$ ，且 $y\ R\ x$ ，则 $x=y$ ；
传递性：对任意 $x,y,z\in A$ ，若 $x\ R\ y$ ，且 $y\ R\ z$ ，则 $x\ R\ z$ 。
那么，关系 $R$ 就是一种偏序关系。

拟序关系：指没有自反性的偏序关系。

举个例子：“ $\leq$ ”就是一种偏序关系，因为它具有自反性（ $x\leq x$ ），具有反对称性（ $x\leq y,\ y\leq x,\ \Rightarrow x=y$ ），也具有传递性（ $x\leq y,\ y\leq z,\ \Rightarrow x\leq z$ ），而 $<$ 则不是偏序关系，它是一种拟序关系。

前置知识：分治。

二维偏序

二维偏序，即在两个序列 $a$ 和 $b$ 中，同时满足两种给定的偏序/拟序关系 $R_1,\ R_2$ 的数对 $\{i,j\}$ 的数量，即满足 $a_i\ R_1\ a_j$ ， $b_i\ R_2\ b_j$ 的方案总数。

例题

给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i<j$ 且 $a_i>a_j$ ，则其为一个逆序对；否则不是。

做法 $1$ ：数据结构维护

思路

求解方式非常简单，即从后往前遍历 $a_i$ 中的每个元素，求其后面（ $i<j$ ）共有多少个 $j$ 满足 $a_i>a_j$ 。

实际上，求 $<a_i$ 的数字总数，那么就考虑采用正确的更新顺序，先保证一维满足偏序/拟序关系，再通过数据结构查询另一位偏序/拟序关系，发现数组下标的偏序/拟序关系很容易维护，那么，考虑从前向后遍历，保证所有数组下标都是逆序的，然后另一位权值 $a$ 的关系，只要靠树状数组求 $<a_i$ 的元素的前缀和就可以了，或者开值域线段树每次求 $[0,{a_i}-1]$ 的权值和即可。

总共 $n$ 次修改， $n$ 次查询，总的时间复杂度为 $O(n\log n)$ 。

注意，如果数据范围较大，需要先离散化再进行计算，因为有可能开不下这么大的数组，下面的代码以树状数组为例：

参考代码

#include <bits/stdc++.h>
#define int long long
#define lowbit(i) (i&-i)
using namespace std;
const int N = 2e5+7;
struct node {
	int tr[N];
	void update(int x,int y) {
		for(int i=x;i<N;i+=lowbit(i))
			tr[i]+=y;
	}
	int query(int x) {
		int res=0;
		for(int i=x;i>0;i-=lowbit(i))
			res+=tr[i];
		return res;
	}
} tr;
int a[N];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),
	cout.tie(nullptr);
	int n,res=0;
	cin>>n;
	vector<int> vc;
	for(int i=1;i<=n;++i) cin>>a[i],vc.push_back(a[i]);
	sort(vc.begin(),vc.end()); //先离散化，防止值域太大
	vc.erase(unique(vc.begin(),vc.end()),vc.end());
	for(int i=1;i<=n;++i) a[i]=lower_bound(vc.begin(),vc.end(),a[i])-vc.begin()+1;
	for(int i=n;i>=1;--i) {
		tr.update(a[i],1); //树状数组的查询和更新
		res+=tr.query(a[i]-1);
	} cout<<res<<'\n';
	return 0;
}

做法 $2$ ：分治

思路

这里就要用到分治的思想了，不了解分治的同学请先学习一下分治，学习前置知识。

对区间进行分治，然后进行归并排序，在合并区间时统计逆序对数量。

每次先取区间中点 $mid=\lfloor{{l+r}\over 2}\rfloor$ ，然后分别对区间 $[l,mid]$ 和区间 $(mid,r]$ 分别进行归并排序，进行“分”的操作。

排序结束后，就要开始进行“治”的操作了，由于左边区间和右边区间的数组下标的偏序/拟序关系很容易确定，左边区间的数组下标 $y$ 都在 $[l,mid]$ 之间，右区间的数组下标 $x$ 都在 $(mid,r]$ 之间，所以一位/拟序关系已经解决，即 $x>y$ ，那么另一位偏序/拟序关系可以在双指针合并时进行统计，即在右区间的某个元素 $a_x\ (x\in (mid,r])$ 被归并进区间时，查询左边还有多少个 $a_y\ (y\in [l,mid])$ 没有被归并进区间，由于归并排序按照从小到大依次放入新区间，所以可以保证 $a_x<a_y$ ，那么，我们就可以保证 $x>y$ 且 $a_x<a_y$ 的所求偏序/拟序关系的数对数量了。

在这种做法当中，不需要进行离散化。

参考代码

#include <bits/stdc++.h>
#define int long long
#define lowbit(i) (i&-i)
using namespace std;
const int N = 2e5+7;
int n;
int a[N],b[N];
int merge_sort(int a[],int l,int r) {
	if(l==r) return 0;
	int mid=l+r>>1,zc=l;
	int ans=merge_sort(a,l,mid)+merge_sort(a,mid+1,r);
	//分治归并做右区间，先将答案设为左右区间各自产生的答案
	int i=l,j=mid+1;
	for(;j<=r;++j) {
		while(a[i]<=a[j]&&i<=mid) b[zc++]=a[i++];
		ans+=mid-i+1,b[zc++]=a[j];
		//在合并区间时统计答案，保证另一维的偏序关系
	} while(i<=mid) b[zc++]=a[i++];
	//双指针合并左右区间，保证区间有序，方便合并
	for(int i=l;i<=r;++i) a[i]=b[i];
	return ans;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	int res=merge_sort(a,1,n); //进行归并排序
	cout<<res<<'\n';
	return 0;
}

总体思想

由上述分治和数据结构维护两种方法不难看出，解决多维偏序/拟序问题的方式都是先保证一维有序，然后在有序的这一维上按照顺序对于第二维进行更新，再对第二维进行查询，从而求出答案。

三维偏序

三维偏序是基于二维偏序，用给定另一个偏序/拟序关系 $R_3$ ，求解满足三个条件的序列方案总数，它的别称非常具有诗意——陌上花开（关于为什么叫这个名字，我查了好久，都没有得到结果）。

例题

有 $n$ 个元素，第 $i$ 个元素有 $a_i$ 、 $b_i$ 、 $c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j\leq a_i$ 且 $b_j\leq b_i$ 且 $c_j\leq c_i$ 的 $j$ 的数量。

对于 $d\in[0,n)$ ，求 $f(i)=d$ 的 $i$ 的数量。

原题 & 提交链接：洛谷 P3810 【模板】三维偏序（陌上花开） 。

思路

刚才解决二维偏序的时候，我讲解了两种做法，分治和数据结构维护两种，那么，当维数达到三维时，我们可以考虑两者同时使用，我们中国一位伟大的 OIer 陈丹琦同学基于这个想法发明了一种分治方法，即 cdq 分治，可以用于偏序/拟序问题降维，其核心思路为：通过先排序，再分治，消掉一位，然后再对分治后的左后区间再次进行排序，然后进行独立的二维偏序求解即可。

比如在这题中，我们要求 $a_j\leq a_i$ 且 $b_j\leq b_i$ 且 $c_j\leq c_i$ 的数对数量，那么考虑先按照 $a$ 进行排序，排序过后，对一个区间 $[l,r]$ ，进行以下操作：

取区间中点 $mid$ ，先将区间拆成 $[l,mid]$ 和 $(mid,r]$ ，由于 $a$ 数组有序，假设 $x\in [l,mid]$ ， $y\in (mid,r]$ ，那么不难知道 $a_x\leq a_y$ ，通过分治保障了第一维是有序的。
对于左右区间 $[l,mid]$ 和 $(mid,r$ 进行分别的求解计算。
归并左右区间，合并时，如果我们直接进行归并式的合并，那么会导致 $a_x$ 与 $a_y$ 的关系很难确定，所以，左右区间是不能直接合并的，考虑 $b$ 和 $c$ 的关系，可以在将左、右区间分别进行排序，在两区间中使用双指针 $i$ 和 $j$ 进行滑动（假设 $i$ 是左区间中的指针， $j$ 是右区间中的指针），那么可以通过移动指针 $i$ 和 $j$ ，使得 $b_i$ 和 $b_j$ 恒满足偏序/拟序关系，即 $b_i\leq b_j$ ，那么，对于 $c_i$ 和 $c_j$ 的偏序/拟序关系，可以使用数据结构来维护。

警钟长鸣：一定要去重！

对于下面这个样例，可以在不去重的情况手算答案：

可以发现，在不去充的情况下算出的结果是 1 1 1，而正确结果是 0 0 3（这里为了节省空间，将换行改为了空格），这是为什么呢？

可以发现，我们的 cdq 分治对于左右区间合并的时候，左区间的值可以对右区间产生贡献，但是右区间永远不能对左边产生贡献，也就是说，如果 $i<j$ ，那么如果 $x_i$ 和 $x_j$ 的所有值都相同，那么根据偏序的反对称性，不论是 $x_i$ 对 $x_j$ ，还是 $x_j$ 对 $x_i$ ，都满足偏序关系，所以都应对对方产生贡献，而由于 $i<j$ ，所以只有 $i$ 对 $j$ 产生了贡献， $j$ 对 $i$ 并没有产生贡献，为了解决这个问题，只能通过去重，将相同元素合并成一个，这样所有元素之间都不存在“等于”的关系，偏序就变成了拟序，于是就可以正常求解了。

但是，如果是拟序关系，那么就不需要去重了，但是偏序关系必须去重。

参考代码

#include <bits/stdc++.h>
#define int long long
#define lowbit(i) (i&-i)
using namespace std;
const int N = 2e5+7;
int a[N],res[N],cnt[N];
struct node {
	int a,b,c,id,ct=0;
} x[N],zc[N]; //结构体存储
bool cmp(node a,node b) {
	if(a.a!=b.a) return a.a<b.a;
	if(a.b!=b.b) return a.b<b.b;
	return a.c<b.c;
	//先按照关键字 a 进行排序
}
struct trnode {
	int tr[N];
	void update(int a,int b) {
		for(int i=a;i<N;i+=lowbit(i))
			tr[i]+=b;
	}
	int query(int a) {
		int res=0;
		for(int i=a;i>0;i-=lowbit(i))
			res+=tr[i];
		return res;
	}
} tr; //树状数组
void merge_sort(int l,int r) {
	if(l==r) return;
	int mid=l+r>>1;
	merge_sort(l,mid),merge_sort(mid+1,r); //分治两个区间
	int i=l,j=mid+1;
	for(;j<=r;++j) {
		while(x[i].b<=x[j].b&&i<=mid)
			tr.update(x[i++].c,x[i].ct);
		res[x[j].id]+=tr.query(x[j].c);
		//区间合并时，进行树状数组更新和查询
	} --i;
	for(;i>=l;--i) //还原树状数组形态
		tr.update(x[i].c,-x[i].ct);
	int pos=l;
	i=l,j=mid+1;
	for(;i<=mid&&j<=r;) {
		while(x[i].b<x[j].b&&i<=mid) zc[pos++]=x[i++];
		zc[pos++]=x[j++];
	} while(i<=mid) zc[pos++]=x[i++];
	for(int i=l;i<=r;++i) x[i]=zc[i];
	//归并左右区间，并按照 b 关键字进行排序
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),
	cout.tie(nullptr);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;++i) cin>>zc[i].a>>zc[i].b>>zc[i].c;
	sort(zc+1,zc+n+1,cmp);
	int idx=0;
	for(int i=1;i<=n;++i)
		if(zc[i].a==zc[i-1].a&&zc[i].b==zc[i-1].b&&zc[i].c==zc[i-1].c) x[idx].ct++;
		else x[++idx]={zc[i].a,zc[i].b,zc[i].c,idx,1}; //去重并计数
	//for(int i=1;i<=idx;++i) cout<<x[i].a<<' '<<x[i].b<<' '<<x[i].c<<' '<<x[i].id<<' '<<x[i].ct<<'\n';
	merge_sort(1,idx); //归并求答案
	for(int i=1;i<=idx;++i) cnt[res[x[i].id]+zc[i].ct-1]+=zc[i].ct;
	//之所以 +zc[i].ct-1，是因为一个数与其自身也是满足偏序关系的
	for(int i=0;i<n;++i) cout<<cnt[i]<<'\n';
	return 0;
}

偏序问题与 CDQ 分治

什么是偏序和拟序？

二维偏序

例题

做法 111：数据结构维护

思路

参考代码

做法 222：分治

思路

参考代码

总体思想

三维偏序

例题

思路

警钟长鸣：一定要去重！

参考代码

感谢您的支持，我会继续努力的!

做法 $1$ ：数据结构维护

做法 $2$ ：分治