CDQ分治

CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。

CDQ分治的思想常用于离线解决点对之间的问题，最经典的如三维偏序。

解决这类问题的过程为：

• 将序列 $ (l, r) $ 分为。

• 递归处理序列$ (l, mid) $ 和 $ (mid + 1, r) $中的答案。

• 设计算法处理对于点对

$ \color {skyblue}P3810 \text【模板】三维偏序（陌上花开）$

题意

有 $ 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 \ne i $ 的 \(j\) 的数量。

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

思路

考虑先将数组按 $ a $ 排序，然后开始分治。

假设当前在处理区间 \(l, r\) ，并且已经统计完的答案，那么就要思考如何处理点对 $ (i, j) (l \le i \le mid), (mid + 1 \le j \le r) $ 间的答案。

首先由于开始时已将数组按 $ a $ 排序，所以左区间内的所有点的 $ a $ 都小于右区间。

那么对于 $ j \in [mid + 1, r] $ , $ f(j) $ 应加上 $ b_i \le b_j $ && $ c_i \le c_j $ $ (i \in [l, mid]) $ 的数量。

为了处理第二维 $ b $ ，我们可以将区间 $ (l, mid) $ 和 $ (mid + 1, r) $ 都按 $ b $ 排序，然后使用双指针维护 $ b_i \le b_j $。

维护第三维 $ c $ , 我们可以使用树状数组。

在 $ i $ 指针向右移的过程中，我们把树状数组中 $ c_i $ 位上 $ +1 $，这样更新 $ f(j) $ 时只需在树状数组中查询 $ \le c_j $ 的个数即可。

注意：进入递归前需要对原数组进行去重，否则会出错。

代码

#include<bits/stdc++.h>
#define int long long
#define Debug puts("Oops!")
using namespace std;

const int N = 2e5 + 5, M = 5e5 + 5;

int n, m, k;
int res[N];

struct sb {
	int x, y, z;
	int cnt, f;
}p[N], a[N]; 

struct BIT {
    int t[N];
    int lowbit(int x) {return x & -x;}
    void add(int x, int c) {for(; x <= k; x += lowbit(x)) t[x] += c;}
    int ask(int x) {int res = 0;for(; x; x -= lowbit(x)) res += t[x]; return res;}
}T;

bool cmp1(sb x, sb 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;
}

bool cmp2(sb x, sb y) {
	if(x.y != y.y) return x.y < y.y;
	return x.z < y.z;
}

void cdq(int l, int r) {
    if(l == r) return ;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
	sort(a + l, a + mid + 1, cmp2), sort(a + mid + 1, a + r + 1, cmp2);
	int i = l, j = mid + 1;
	while(j <= r) {
		while(i <= mid && a[i].y <= a[j].y) T.add(a[i].z, a[i].cnt), i++;
		a[j].f += T.ask(a[j].z);
		j++;
	}
	for(int k = l; k < i; k++) T.add(a[k].z, -a[k].cnt);
}

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
	while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
	return x * f;
}

signed main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = read(), k = read();
	for(int i = 1; i <= n; i++)	p[i].x = read(), p[i].y = read(), p[i].z = read();
	sort(p + 1, p + 1 + n, cmp1);
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		cnt++;
		if(p[i].x != p[i + 1].x || p[i].y != p[i + 1].y || p[i].z != p[i + 1].z)
			a[++m].x = p[i].x, a[m].y = p[i].y, a[m].z = p[i].z, a[m].cnt = cnt, cnt = 0;
	}
    cdq(1, m);
	for(int i = 1; i <= m; i++) res[a[i].f + a[i].cnt] += a[i].cnt;
	for(int i = 1; i <= n; i++) cout << res[i] << endl;
	return 0;
}