题解：P3810 【模板】三维偏序（陌上花开）

本题解使用 CDQ 分治做法。

什么是 CDQ 分治？

CDQ 分治是由

2008

年 IOI 金牌得主陈丹琦在高中时整理并总结的一种分治思想¹，可以用于解决偏序问题、一些动规的优化、离线按时间顺序处理等。

CDQ 分治最经典的应用就是处理一些点对

(i,j)(i \le j)

，此时它的主要思想如下：

把序列从 $mid$ 切开，分成两半；
把点对分成三类：
- 第一类是 $j \le mid$ ，即都在左半部分；
- 第二类是 $i > mid$ ，即都在右半部分；
- 最后一类是横跨 $mid$ 的部分。
左右两半分别递归，处理前两类点对。
想办法处理最后一类点对。

以本题为例，本题是要找到一些点对满足偏序关系。

首先我们可以对第一维

a

进行排序，这样序列后面的数一定大于序列前面的数，我们就可以少处理一维。

接着，我们在处理第二维的时候进行 CDQ 分治。

对于一个

[l,r]

的区间，我们可以如此做：

首先先处理 $[l,mid]$ 和 $(mid,r]$ 。（ $mid$ 是区间中点）
- 如果 $l=r$ ，那么一定没有贡献，可以直接返回。
然后，我们处理左端点在 $[l,mid]$ ，右端点在 $(mid,r]$ 的点对的贡献。
- 由于我们已经按 $a$ 排好序，所以右区间 $(mid,r]$ 的点的 $a$ 值一定大于左区间。
- 此时我们把两个区间分别按照 $b$ 排序。
  - 这样虽然会打乱区间内 $a$ 的顺序，但是我们只考虑跨区间的贡献。而且区间内的贡献我们在前面已经算完了，后面只会算更大块区间的两侧贡献，而大块之间的 $a$ 的顺序并不会被排序影响。
- 然后我们用树状数组+双指针法处理 $c$ 的偏序关系。
  - 由于我们只要算跨区间的贡献（ $b_i,c_i$ 都小于 $b_j,c_j$ ，且 $i$ 在左区间、 $j$ 在右区间的点对 $i,j$ 个数），所以树状数组上第 $i$ 位存 $c_x=i$ 的 $x$ 在左区间出现了多少次。（需要离散化）
  - 我们两个指针 $x,y$ 分别扫左区间和右区间。当 $y$ 增加后，我们把满足 $b_x \le b_y$ 的 $c_x$ 都加入树状数组。由于 $b$ 是有序的，所以可以用一个指针扫。等到所有满足条件的 $c_x$ 都加入树状数组后，我们只需查询树状数组上 $1 \sim c_y$ 的前缀和即是右端点为 $y$ 的贡献。
然后我们退回上一层，继续这样操作，直到求出所有答案。

这就是本题的 CDQ 分治思路。

正确性 & 时间复杂度分析

由于我们开始对

a

排好了序，而我们是从下到上 CDQ 分治的，所以

a

这一维的偏序可以保证正确。

然后，我们对

b

进行排序，使用双指针确保加入树状数组的数的

b

值都小于要求贡献的数的

b

值。

最后，查询树状数组中的

1 \sim c_y

的前缀和，由于是把左区间的数加入树状数组，所以可以保证不重复。

时间复杂度：

离散化 & $a$ 排序： $O(n \log n)$
对于 CDQ 分治：
- $b$ 排序 & 树状数组： $O(n \log n)$
- 总时间复杂度： $T(n) = O(n \log n) + 2T(\frac n 2) = O(n \log^2 n)$

所以时间复杂度是

O(n \log^2 n)

。

常数优化

对

b

排序如果每次都用 sort，常数较大。我们发现因为我们在往下递归的时候完成了左右两部分的

b

的排序，所以我们在这层可以直接把这两部分归并，在排序部分做到

O(n)

，这样总时间复杂度的第二个

\log

就只有树状数组的小常数

O(n \log n)

。

实现细节

记得清空树状数组！！！ 不能使用暴力清空（时间复杂度会变成 $O(n^2 \log n)$ ），怎么加入的怎么清空（实在不理解你可以再来一遍双指针，但是不要再统计一遍答案）
要去重！！！ 重复的元素可以互相贡献，但是上述算法处理不了重复元素（只会算一次贡献）。去重后树状数组要加上这个元素的个数。
前面对 $a$ 排序时 $a$ 相等要对 $b$ 排序， $b$ 也相等要对 $c$ 排序。CDQ 内对 $b$ 排序， $b$ 相等时可以不用对 $c$ 排序。（请读者思考一下为什么²）
还是不对？看看讨论区“警示后人”。

代码实现

CPP

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, A = 2e5 + 5;

struct node{
	int ans, gs;
	int a, b, c;
};

node a[N], b[N];
int n, _n, k, bowl[N];
long long ans[N];

// 对a排序 
bool cmp(node x, node y){
	// 注意a/b相等时的处理 
	if(x.a == y.a) 
		if(x.b == y.b) 
			return x.c < y.c;
		else
			return x.b < y.b;
	return x.a < y.a;
}
// cdq内对b排序 
bool cmp2(node x, node y){ 
	/*if(x.b == y.b)
		return x.c < y.c;*/
	// 上面这个if可要可不要 
	return x.b < y.b;
}

// 树状数组 
struct treez{
	int t[A];
	int find(int x){
		int ans = 0;
		for(; x; x -= (x & (-x))) ans += t[x];
		return ans;
	}
	void add(int x, int y){
		for(; x <= 2e5; x += (x & (-x))) t[x] += y;
	}
} tr;

//cdq主体 
void cdq(int l, int r){
	if(l == r) return ;
	int mid = (l + r) >> 1;
	
	// 1.递归左右 
	cdq(l, mid), cdq(mid + 1, r);
	
	// 2.排序 
	sort(a + l, a + mid + 1, cmp2), sort(a + mid + 1, a + r + 1, cmp2);
	
	// 3.双指针求贡献 
	int i = l, j = mid + 1;
	for(; j <= r; ++j){
		while(i <= mid && a[i].b <= a[j].b) tr.add(a[i].c, a[i].gs), i++;
		a[j].ans += tr.find(a[j].c);
	}
	
	// 4.清空树状数组 
	for(int k = l; k < i; ++k){
		tr.add(a[k].c, -a[k].gs);
	}
}

int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d%d%d", &b[i].a, &b[i].b, &b[i].c);
		
	sort(b + 1, b + n + 1, cmp);
	
	// 神秘の去重 
	int w = 0;
	for(int i = 1; i <= n; ++i){
		++w;
		if(b[i].a != b[i + 1].a || b[i].b != b[i + 1].b || b[i].c != b[i + 1].c){
			a[++_n] = b[i];
			a[_n].gs = w;
			w = 0;
		}
	}
	
	cdq(1, _n);
	
	// 相同数字可以重复贡献，别忘了加上 
	for(int i = 1; i <= _n; ++i) bowl[a[i].ans + a[i].gs - 1] += a[i].gs;
	
	for(int i = 0; i < n; ++i) printf("%d\n", bowl[i]);
	return 0;
}

Footnotes

从《Cash》谈一类分治算法的应用 ↩
前者可能导致 $b(c)$ 更大的被分在左区间，而后者由于加入树状数组的先后顺序/查询的先后顺序没有影响，所以后者不在相等时排序 $c$ 也是可以的。 ↩

题解：P3810 【模板】三维偏序（陌上花开）

文章操作

什么是 CDQ 分治？

正确性 & 时间复杂度分析

常数优化

实现细节

代码实现

Footnotes

相关推荐

评论

题解：P3810 【模板】三维偏序（陌上花开）