剑圣的苦恼 CDQ分治入门
缘起
剑圣非常在意自己的实力排名，所以剑圣想知道力量, 敏捷, 智力皆在自己之下的英雄有多少个? 你能帮帮他吗?
分析
洛谷 P3810 模板 三维偏序 陌上花开
题目背景
这是一道模板题，可以使用 bitset，CDQ 分治，KD-Tree 等方式解决。
题目描述
有 n 个元素，第 i 个元素有 a_i,b_i,c_i 三个属性，设 f(i) 表示满足
a_j <= a_i && b_j <= b_i && && c_i <= c_j && j != i
的 j 的数量，特别的，我们称 j 在偏序意义下 < i, f(i) 其实就是偏序意义下 < i 的点的个数.
对于 0 <= d < n，求 f(i) = d 的数量
【输入】
第一行是两个整数 n 和 k, 分别表示元素的数量和最大属性值.
接下来 n 行, 每行三个整数 ai, bi, ci 分别表示三个属性值.
【输出】
n行，第 d + 1 行表示 f(i) = d 的数量
【样例输入】
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
【样例输出】
3
1
3
0
1
0
1
0
0
1
【数据规模说明】
1<=n<=1e5, 1<=a_i, b_i, c_i <=k <= 2e5
【限制】
1s 500MB先不谈CDQ分治，我们先谈谈分治，分治本质上就是自顶向下的通过不断的将问题分解为更小的子问题——直至问题平凡可解，然后再自底向上归并答案. 例如归并排序、快排、FFT等等都是这样.
下面分析一下分治算法的复杂度. 因为分治是通过不断的二分缩小问题规模，所以分治的次数是 的, 即树高 , 而树的每层的节点包含的元素总个数都是 n , 所以如果每次分治处理 这n个元素的复杂度是 O(n) 的话，则分治算法的复杂度就是 ，如果每次分治处理这n个元素的复杂度是 的话，则该分治算法的复杂度就是 , 看出什么没有? 分治的代价就是复杂度多挂一个 . 即
箭头左边是处理n个元素的复杂度，箭头右边是杂糅进分治之后的复杂度.
讲完了分治，那么CDQ分治是什么呢? 先膜一发 CDQ 女神哈~ or2222222222222222222
先声明一下CDQ分治能解决的典型问题: 三维偏序问题（偏序的概念详见《离散数学》）,本题就是一个典型的三维偏序问题.
那么如果我们不会CDQ分治，本题该怎么解? 三维难想，就先从一维开始想起.
即如果本题不是三维偏序，仅仅是一维偏序的话，就太容易了，一个sort就完了. 事实上，一维偏序就是全序.
如果是二维偏序呢? 也不难，就是 离线+树状数组+扫描线思想，我们先按照一维排序，然后按照此顺序遍历所有的点——不断的将点加入到树状数组中（这就是扫描线思想），然后维护树状数组并回答询问即可.
现在考虑三维偏序问题，我们理所当然的先按照一维进行排序，则这一维就可以不用考虑了，相当于排序给我们降了1维，还剩下2维，于是我们想效仿我们上面处理二维偏序的方法，但是现在我们加入的是二维的点而不是一维的点，所以不能使用一维的树状数组，而只能使用二维的树状数组? 但是二维树状数组的劣势是显然的——的空间复杂度分分钟原地爆炸. 不能使用二维树状数组维护加入的二维点的话，就只能考虑使用树套树，确切讲是树状数组套线段树来维护加入的二维点——空间复杂度, 时间复杂度 ，自带巨大常数，被 T 或者 MLE 的隐患相当高.
综上所述，我们只能使用树套树来维护加入的二维点集，但是众所周知，树套树是我们必须学会但是考试的时候一定要尽量避免的数据结构，所以才有了分块、莫队、CDQ分治等等神仙算法的百家齐放~
怎么办呢? 神犇救世~ CDQ 发明了 CDQ 分治.
CDQ 分治的初心就是不想使用树套树这种时空常数巨大、容易手滑打错、较难调试的二维数据结构. 和分块、莫队等算法的初心是一样的~
那么CDQ分治是怎么实现初心的呢? 回归到本题，首先，我们只需要计算出每个 f[i] 即可，下面称 f[i] 为 i 处的答案. 如果知道了每个 f[i] 的值，则得出答案易如反掌~ 那么怎么计算 f[i] 呢?
先将所有的点按照一维（称此维为X，其余2维称为 Y 和 Z）升序排序，然后将整个序列二分为两段进行分治，我们称X较小的那一段为L，称X较大的那一段为R，众所周知，分治的核心在于答案的归并， 所以我们必须计算 L 中的点对 R 中的点处答案的贡献（下面简称为 L 对 R的贡献）. 因为已经按照X升序排好了序，所以 L 中任何一个点的X坐标一定 R中任意一点的X坐标, 所以如果L中的一个点A能对R中的一个点B处的答案有贡献的话，那么一定有 , 所以我们将 L 和 R 分别按照 Y 坐标升序排序，然后简单的使用一个双指针的技巧就可以在 时间内对于每个 R 中的点 B 找到
于是，CDQ算法的高潮来了（其实和 离线+树状数组+扫描线 的思想如出一辙），对于 任何 , 在用双指针找 MAX(B) 的过程中，不断的将遍历到的L中的点的Z坐标用一维的树状数组维护起来，然后就可以使用该树状数组在 时间内得到 L 中全部的点对 R中的一个点 B 的贡献. 所以CDQ分治归并答案的复杂度是 ，所以CDQ分治的总时间复杂度是 ，空间复杂度显然是 ，虽然复杂度和树套树一样，但是因为过程中使用的是一维树状数组，所以常数会比树套树小得多，事实上，跑的也会比树套树快的多~ 代码实现细节上，因为每次分治使用的都是同一个树状数组，所以每次分治完成之后都要将树状数组清零，这个需要注意一下.
不用担心，代码比解释清楚的多，后面写完代码我还会详细注释一波~
看到了没有? CDQ 分治巧妙的通过引入分治，将原本需要二维数据结构——树套树介入的三维偏序问题降了一维，变成只需要一维数据结构树状数组就能解决的问题了！事实上，我们常常使用 离线 + 排序 + CDQ 分治 + 树状数组来解决高维偏序问题. 所以有的网上教程也称之为 CDQ 分治套树状数组. 这个套字体现在分治归并使用到了树状数组这种数据结构上，所以如果处理分治的归并用的是线段树的话，那就叫CDQ套线段树，如果用的是分块，那就叫CDQ套分块。。。
下面切代码
//#include "stdafx.h"
//#define LOCAL
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <string>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <map>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define re register int
typedef pair<int, int> P;
#define FE(cur) for(re h = head[cur], to, len; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define ilp inline P
#define LEN(cur) (hjt[cur].r - hjt[cur].l)
#define MID(cur) (hjt[cur].l + hjt[cur].r >> 1)
typedef vector<int>::iterator vit;
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), *pr2 = 0, pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
ilv read(int &x)
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
ilv read(char *x)
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv readln(char *x)
{
char c = gc();
while(c == 10) c = gc();
while(c >= 32 && c <= 126) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
ilv write(char c) { pc(c); }
ilv writeln(char c) { write(c); pc(10); }
} using namespace fastio;
const int maxn = 2e5+5;
int n, k, a[maxn], ans[maxn], cnt[maxn], tot, num[maxn];
struct T
{
int x, y, z, id, cnt;
} ts[maxn];
bool cmpx(const T &a, const T &b)
{
if (a.x ^ b.x)
{
return a.x < b.x;
}
if (a.y ^ b.y)
{
return a.y < b.y;
}
return a.z < b.z;
}
bool cmpy(const T &a, const T &b)
{
return a.y < b.y;
}
ili lowbit(int i)
{
return i & -i;
}
ilv upd(int i, int d)
{
while (i <= k)
{
a[i] += d;
i += lowbit(i);
}
}
ili que(int i)
{
int ans = 0;
while (i)
{
ans += a[i];
i -= lowbit(i);
}
return ans;
}
void cdq(int l, int r)
{
if (l == r) return;
int mid = l + r >> 1;
cdq(l, mid), cdq(mid + 1, r);
sort(ts + l, ts + mid + 1, cmpy), sort(ts + mid + 1, ts + r + 1, cmpy);
int j = l;
for (re i = mid + 1; i <= r; i++)
{
for (; j <= mid && ts[j].y <= ts[i].y; j++)
{
upd(ts[j].z, ts[j].cnt);
}
ans[ts[i].id] += que(ts[i].z);
}
for (re i = l; i < j; i++)
{
upd(ts[i].z, -ts[i].cnt);
}
}
signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
// freopen("d:\\my.out", "w", stdout);
#endif
read(n), read(k);
for (re i = 1; i <= n; i++) read(ts[i].x), read(ts[i].y), read(ts[i].z);
sort(ts + 1, ts + n + 1, cmpx);
int c = 1;
for (re i = 1; i <= n; i++)
{
if (ts[i].x == ts[tot].x && ts[i].y == ts[tot].y && ts[i].z == ts[tot].z)
{
++c;
}
else
{
++tot;
ts[tot] = ts[i];
num[tot - 1] = ts[tot - 1].cnt = c, ts[tot - 1].id = tot - 1;
c = 1;
}
}
num[tot] = ts[tot].cnt = c, ts[tot].id = tot;
cdq(1, tot);
for (re i = 1; i <= tot; i++)
{
cnt[ans[i] + num[i] - 1] += num[i];
}
for (re i = 0; i < n; i++)
{
writeln(cnt[i]);
}
flush();
return 0;
}ac情况
Accepted | 847ms | 6.48MB下面解释一下上面代码的一些细节. 首先，因为题目中的数据可能存在重复的点，例如下面这种数据
2 3
1 3 1
1 3 1则答案显然是
0
2如果不进行去重，则得到的答案就是
1
1原因是这样的，我们称第一个 (1,3,1) 点为 A, 第二个 (1,3,1)点为B, 则假设排序后 A在 B 前面, 则偏序意义下比A小的点就是0个，偏序意义下比B小的点的个数是1个, 所以答案如上. 这不就错了么? 所以我们要将 两个(1,3,1)点合成一个点，这个点的重复次数是2（这个2就是下面数据结构的cnt域）. 所以我们本题设计的数据结构如下
struct T
{
int x, y, z, id, cnt; // id 表示原先是哪个点, cnt 表示此点有多少个
}下面讲一下cdq的代码
line 72 ~ 88
一定要按照X是第一关键字, Y是第二关键字, Z是第三关键字进行排序, 漏掉任何一个关键字都是错误的.
为什么? 以一组数据就足以说明问题了
4 3
3 3 3
3 1 1
3 1 1
3 3 1
如果只以X为关键字排序, 可能排序为(sort api是不稳定排序)
3 3 3 2 1 （依次是 x、y、z、id、cnt）
3 3 1 2 1
3 1 1 3 2
那么分治就会将 Y 大的 3 3 3 2 1 和 3 3 1 2 1 将被分治到L中去, 而Y小的 3 1 1 3 2 反而分治到R中去了，
L、R的含义前文已经说过了, 那么 3 3 3 2 1 和 3 3 1 2 1 将无法得到 3 1 1 3 2 的贡献. 答案就错了.
类似的, 如果只以X为第一关键字, Y为第二关键字进行升序排序也是错误的, 因为可能排序为
3 1 1 3 2
3 3 3 2 1
3 3 1 2 1
那么 3 1 1 3 2 和 3 3 3 2 1 被分治到 L 中去, 3 3 1 2 1 被分治到 R 中去了. 那么
3 3 3 2 1 因为在 L中而将吃不到 3 3 1 2 1 的贡献, 答案也就错了.
综上, X、Y、Z 一个都不能少! 那么为什么 87行的排序规则可以仅仅按照 Y 坐标升序排序呢? 这是因为144行已经
按照 X、Y、Z 升序排序过了, 自底向上归并答案的时候无需担心Z大的吃不到Z小的点的贡献.所以120行仅仅依据Y升序
排序即可.
line 117
这是递归的出口, 这是通识
line 119
分治
line 120
对L和R分别按照Y进行排序.
line 122 ~ 124
双重 for 里面的 i 和 j 就是前文所说的双指针. 内层的for循环就是在求MAX(B) 的过程.
line 126
就是在求 MAX(B) 的过程中不断将遍历到的点的Z坐标用树状数组维护起来.
line 128
因为有了树状数组的维护，我们一旦完成了 MAX(B) 的求解, 就可以 O(log n)时间计算 L中所有的点对
R中一个点(即 ts[i].id 这个点) 的贡献.
line 130 ~ 133
因为所有分治归并的过程中使用的都是同一个树状数组, 所以这个树状数组要在完成一次分治之后清零. 如果不卡时间
完全可以 memset(a, 0, sizeof(a)), 但是实测发现会被 T, 所以用这里的方法清零好了.小结
诚然，纵观CDQ分治的整个过程，其实就是分治，甚至没什么特别之处（网上有一些大佬说CDQ的特别之处在于L分治对R分治答案有影响，其实私以为这只是一般分治过程中答案归并的技术细节，这是不能限定死的.），但是为什么会为她独家命名? 不仅仅是因为CDQ女神漂亮，而是因为CDQ 巧妙的使用了分治算法将原本要使用二维数据结构（树套树）来求解的三维偏序问题降了1维，成为只需要使用一维树状数组就可以搞定的问题。直接后果就是码量的大幅降低，复杂度还丝毫不虚——众所周知，一维数据结构中最为推崇的就是树状数组，不仅码量巨少，而且性能巨高。CDQ分治之所以被特别冠名，不是因为她发明了一种新的分治算法，而是惊艳的使用了传统的分治算法大幅降低了三维偏序问题的求解难度。
腾讯云开发者
