CDQ 分治学习笔记
概念
- \(k\) 维偏序：
- 在一个由 \(k\) 元组构成的集合 \(A\) 当中，一般用 \(\prec\) 表示的一种二元关系。
- 具有自反性、反对称性、传递性的二元关系。
- 自反性：\(\forall x \in A,x \prec x\)；
- 反对称性：若 \(x \prec y\) 且 \(y \prec x\)，有 \(x = y\)；
- 传递性：若 \(x \prec y\) 且 \(y \prec z\)，有 \(x \prec z\)。
- 如 \(\le\) 就是一种偏序。
三维偏序问题
引入
给定一个序列，每个点有 \(a_i\)，\(b_i\)，\(c_i\) 三个属性，试求：这个序列里有多少对点对 \((i, j)\) 满足 \(a_j \le a_i\) 且 \(b_j \le b_i\) 且 \(c_j \le c_i\) 且 \(i \ne j\)。
思路
我们可以先按 \(a\) 排个序，这样就只剩下了 \(b\) 和 \(c\)，我们可以通过分治的思想，先处理 \(L \sim mid\)，再处理 \(mid + 1 \sim R\)，最后处理他们之间的影响。
像这种分治的思想，就叫 CDQ 分治。
回到这道题，前面两种直接往下递归即可，可是最后一种怎么办呢？
我们可以在分治的时候提前把 \([L, mid]\) 和 \([mid + 1, R]\) 按 \(y\) 排好序，用双指针合并。
此时顺手把左半截的 \(z\) 插入到树状数组中，在右半截的地方记录答案，就做完了。
注意要离散化 \(z\)（因为是严格偏序）。
例题
CF1045G AI robots。
思路
按 \(r\) 降序排序后，转换一下条件（去绝对值）可得：
\[\left\{
\begin{array}{lr}
x_j - r_j \le x_i \le x_j + r_j
\\
q_j - k \le q_i \le q_j + k
\end{array}
\right.
\]
直接 CDQ 分治即可。
代码
AI 加注释。
#include <bits/stdc++.h>
#define il inline
#define pii pair<int, int>
#define ppp(QWQ, QAQ) pair<QWQ, QAQ>
#define pb emplace_back
#define pf emplace_front
#define mpa make_pair
#define pqs(QWQ) priority_queue<QWQ, vector<QWQ>, greater<QWQ> >
#define pqb(QWQ) priority_queue<QWQ>
#define Rep(i, s, e, t) for(int i = (s); i <= (e); i += (t))
#define REP(i, s, e, t) for(int i = (s); i >= (e); i -= (t))
#define debug(a, b) cerr << #a << " = " << a << b;
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) (a) = ((a) < (b) ? (a) : (b))
#define Max(a, b) (a) = ((a) > (b) ? (a) : (b))
#define fi first
#define se second
#define int ll
using namespace std;
using ll = long long;
using ull = unsigned long long;il int read() { int a = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9') { a = a * 10 + ch - '0'; ch = getchar(); } return a * f; }
il void write(int x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); }const int N = 1e5 + 10;
int n, k, _[N], ans = 0;struct AI {int x, r, q, L, R; // x: 离散化后的位置, r: 视野半径, q: 智商, [L,R]: 离散化后的可见区间
} a[N];// 按视野半径降序排序，r 大的在前
il bool cmp(AI i, AI j) { return i.r > j.r; }
// 按智商升序排序，用于 CDQ 合并
il bool cmp1(AI i, AI j) { return i.q < j.q; }// 树状数组，维护位置上的机器人数量
struct BIT{int no[N];#define lowbit(x) (x & -x)il void Modify(int x, int val) { Rep(i, x, n, lowbit(i)) no[i] += val; }il int Query1(int x) { int sum = 0; REP(i, x, 1, lowbit(i)) sum += no[i]; return sum; }il int Query2(int l, int r) { return Query1(r) - Query1(l - 1); }
} bit;/** CDQ 分治解决偏序问题* 当前区间 [l, r] 已经按视野半径 r 降序排列（物理顺序）* 因此左半部分机器人的 r 均大于等于右半部分机器人的 r* 递归处理左右两部分后，统计跨区间贡献：* 对于每个在右半部分（r 较小）的机器人 i，它能看到对方要求距离 <= r_i* 统计左半部分（r 较大）中满足智商差 <= k 且位置在 a[i].L..a[i].R 内的机器人个数* 这些机器人对都会相互交谈（因为右边的能看到左边，左边 r 更大肯定也能看到右边）* 智商条件通过双指针维护：智商在 [a[i].q - k, a[i].q + k] 范围内的左半部分机器人会被加入树状数组* 位置条件通过树状数组查询区间和完成*/
il void CDQ(int l, int r) {if(l == r) return ;int mid = l + r >> 1;CDQ(l, mid); // 递归左半CDQ(mid + 1, r); // 递归右半int L = l, R = l - 1; // L: 左半部分当前移出的位置, R: 左半部分当前加入的位置Rep(i, mid + 1, r, 1) { // 遍历右半部分的每一个机器人// 维护智商下界：将左半部分中智商小于 a[i].q - k 的机器人从树状数组中删除while(!(mid < L) && a[i].q - a[L].q > k) bit.Modify(a[L++].x, -1);// 维护智商上界：将左半部分中智商不超过 a[i].q + k 的机器人加入树状数组while(R < mid && !(a[R + 1].q - a[i].q > k)) bit.Modify(a[++R].x, 1);// 查询左半部分当前在树状数组中的机器人，有多少个位置落在 a[i].L 到 a[i].R 之间ans += bit.Query2(a[i].L, a[i].R);}// 清空树状数组，为上一层 CDQ 准备Rep(i, L, R, 1) bit.Modify(a[i].x, -1);// 将当前区间 [l, r] 按智商重新排序，使上一层合并时左右两部分智商有序sort(a + l, a + r + 1, cmp1);
}signed main() {n = read(), k = read();// 读入每个机器人的原始坐标、视野半径、智商Rep(i, 1, n, 1) _[i] = a[i].x = read(), a[i].r = read(), a[i].q = read();// ---- 离散化坐标 ----sort(_ + 1, _ + n + 1);int lo = unique(_ + 1, _ + n + 1) - _ - 1; // lo 是不同坐标的个数Rep(i, 1, n, 1) {// 计算可见区间离散化后的左右端点// a[i].x - a[i].r 在离散化数组中的下标（第一个 >= 该值的位置）a[i].L = lower_bound(_ + 1, _ + lo + 1, a[i].x - a[i].r) - _;// a[i].x + a[i].r 在离散化数组中的下标（最后一个 <= 该值的位置）a[i].R = upper_bound(_ + 1, _ + lo + 1, a[i].x + a[i].r) - _ - 1;// 将机器人自身坐标也离散化a[i].x = lower_bound(_ + 1, _ + lo + 1, a[i].x) - _;}// 按视野半径降序排序，这样后续 CDQ 中左部分的 r 始终 >= 右部分的 rsort(a + 1, a + n + 1, cmp);CDQ(1, n);write(ans);return (1 ^ 0 ^ 1); // 等效于 return 0;
}