CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，目前这个思想的拓展十分广泛。

让我们来看一个问题

有 $ 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 $ 的数量。$ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。

(资料图)

这是一个三维偏序问题。

偏序问题：给定序列 \(A\)，其中有序对 \((A_i, A_j)\)，满足 \(i < j\) 且 \(A_i < A_j\) 这样的有序对我们称之为逆序对， 信息学竞赛中的逆序对问题，一般是要我们计数给出序列的逆序对个数的总和。其实可以把它看成一个特殊的二维偏序问题，或者说是离散化 \(x\) 坐标的二维偏序问题。

而 CDQ 分治，可以来解决三维偏序问题。上面的引入问题就是模板题 P3810 【模板】三维偏序（陌上花开） 的题意。

变量及其含义

struct node {int x, y, z, cnt, ans;} s1[N], s2[N];

x, y, z: 三个元素。cnt：相同元素的个数。ans：统计答案。

对于第一维 \(a\)，我们可以先从小到大 sort一遍，\(i\) 号点前面的点的 \(a\) 都比 \(a_i\) 小，这样我们就减少了一维的处理，还剩下两维。

bool cmp1(node a, node b) {if (a.x == b.x) {if (a.y == b.y) {return a.z < b.z;}else return a.y < b.y;}return a.x < b.x;}// main() 函数里面n = read(), k = read();mx = k;for (int i = 1, x, y, z; i <= n; ++ i) {x = read(), y = read(), z = read();s1[i].x = x, s1[i].y = y, s1[i].z = z;}sort(s1 + 1, s1 + n + 1, cmp1);

排完序后，我们可以将相同的元素合并为一个元素，结构体里的 cnt就派上用场了。

int top = 0;for (int i = 1; i <= n; ++ i) {++ top;if (s1[i].x != s1[i + 1].x || s1[i].y != s1[i + 1].y || s1[i].z != s1[i + 1].z) {s2[++ m].x = s1[i].x;s2[m].y = s1[i].y;s2[m].z = s1[i].z;s2[m].cnt = top;top = 0;}}

然后处理第二维，对于第二维，我们要求 \(b_j \leq b_i\)，按照前面的思路，我们肯定也要想方设法给第二维排序。我们可以用 归并排序的思想，先分别给左半个区间和右半个区间按照第二维从小到大排序，然后依次处理，由于是在 \(a\) 排好序的基础上进行的在排序，且这两个的区间还没有合并，所以无论怎么打乱，都可以保证左半边元素的 \(a\) 小于等于右半边元素的 \(a\)。对于第三维，相当于到了我们找逆序对的环节了，我们有归并排序和树状数组两种方法，但由于归并排序已经放到前面去处理第二维了，所以我们用树状数组来处理第三维，将节点依次插入树状数组，统计。

bool cmp2(node a, node b) {if (a.y == b.y) {return a.z < b.z;}return a.y < b.y;}void add(int u, int w) {for (int i = u; i <= mx; i += lowbit(i)) {t[i] += w;}}int ask(int u) {int sum = 0;for (int i = u; i; i -= lowbit(i)) {sum += t[i];}return sum;}void cdq(int l, int r) {if (l == r)return ;int mid = (l + r) >> 1;cdq(l, mid);cdq(mid + 1, r);sort(s2 + l, s2 + mid + 1, cmp2);sort(s2 + mid + 1, s2 + r + 1, cmp2);int i, j = l;for (i = mid + 1; i <= r; ++ i) {while (s2[i].y >= s2[j].y && j <= mid) { // 一旦不符合，先统计，然后右指针右移一位。add(s2[j].z, s2[j].cnt); // 插入++ j;}s2[i].ans += ask(s2[i].z);}for (i = l; i < j; ++ i) { // 清空数组,memset 常数太大。add(s2[i].z, -s2[i].cnt);}}

最后就是处理答案了，完整代码：

/*  The code was written by yifan, and yifan is neutral!!! */#include using namespace std;typedef long long ll;#define lowbit(i) (i & (-i))templateinline T read() {T x = 0;bool fg = 0;char ch = getchar();while (ch < "0" || ch > "9") {fg |= (ch == "-");ch = getchar();}while (ch >= "0" && ch <= "9") {x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}return fg ? ~x + 1 : x;}const int N = 1e5 + 5;int n, k, mx, m;int t[N << 1], res[N];struct node {int x, y, z, cnt, ans;} s1[N], s2[N];bool cmp1(node a, node b) {if (a.x == b.x) {if (a.y == b.y) {return a.z < b.z;}else return a.y < b.y;}return a.x < b.x;}bool cmp2(node a, node b) {if (a.y == b.y) {return a.z < b.z;}return a.y < b.y;}void add(int u, int w) {for (int i = u; i <= mx; i += lowbit(i)) {t[i] += w;}}int ask(int u) {int sum = 0;for (int i = u; i; i -= lowbit(i)) {sum += t[i];}return sum;}void cdq(int l, int r) {if (l == r)return ;int mid = (l + r) >> 1;cdq(l, mid);cdq(mid + 1, r);sort(s2 + l, s2 + mid + 1, cmp2);sort(s2 + mid + 1, s2 + r + 1, cmp2);int i, j = l;for (i = mid + 1; i <= r; ++ i) {while (s2[i].y >= s2[j].y && j <= mid) {add(s2[j].z, s2[j].cnt);++ j;}s2[i].ans += ask(s2[i].z);}for (i = l; i < j; ++ i) {add(s2[i].z, -s2[i].cnt);}}int main() {n = read(), k = read();mx = k;for (int i = 1, x, y, z; i <= n; ++ i) {x = read(), y = read(), z = read();s1[i].x = x, s1[i].y = y, s1[i].z = z;}sort(s1 + 1, s1 + n + 1, cmp1);int top = 0;for (int i = 1; i <= n; ++ i) {++ top;if (s1[i].x != s1[i + 1].x || s1[i].y != s1[i + 1].y || s1[i].z != s1[i + 1].z) {s2[++ m].x = s1[i].x;s2[m].y = s1[i].y;s2[m].z = s1[i].z;s2[m].cnt = top;top = 0;}}cdq(1, m);for (int i = 1; i <= m; ++ i) {res[s2[i].ans + s2[i].cnt - 1] += s2[i].cnt;}for (int i = 0; i < n; ++ i) {printf("%d\n", res[i]);}return 0;}

一道比较好的入门题。统计答案的时候稍微麻烦一些。

/*  The code was written by yifan, and yifan is neutral!!! */#include using namespace std;typedef long long ll;templateinline T read() {T x = 0;bool fg = 0;char ch = getchar();while (ch < "0" || ch > "9") {fg |= (ch == "-");ch = getchar();}while (ch >= "0" && ch <= "9") {x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}return fg ? ~x + 1 : x;}const int N = 5e4 + 5;int n;ll ans;struct node {ll v, x;} g[N];bool cmp1(node a, node b) {return a.v < b.v;}bool cmp2(node a, node b) {return a.x < b.x;}void cdq(int l, int r) {if (l == r)return ;int mid = (l + r) >> 1;cdq(l, mid);cdq(mid + 1, r);sort(g + l, g + mid + 1, cmp2);sort(g + mid + 1, g + r + 1, cmp2);ll sum1 = 0, sum2 = 0;for (int i = l; i <= mid; ++ i) {sum2 += g[i].x;}for (int i = mid + 1, j = l; i <= r; ++ i) {while (j <= mid && g[j].x < g[i].x) {sum1 += g[j].x;sum2 -= g[j].x;++ j;}int cnt1 = j - l, cnt2 = mid - j + 1;ans = ans + (cnt1 * g[i].x - sum1 + sum2 - cnt2 * g[i].x) * g[i].v;}}int main() {n = read();for (int i = 1; i <= n; ++ i) {ll v = read(), x = read();g[i] = node{v, x};}sort(g + 1, g + n + 1, cmp1);cdq(1, n);cout << ans << "\n";return 0;}

标签：