【模板】三维偏序（陌上花开）
dongzhenmao
·
2025-08-06 16:36:16
·
题解
似乎题解区并没有 cdq 套 cdq 的作法，刚好今天讲了，就来写一发。
题意与记号
题目讲的很清楚了。此方法并没有树状数组好想也没有其高效，但能很方便扩展。下文记原序列为 d，将每个点拆分成点与询问，内部增加一个名为 id 的数据，若其为 -1，则是点，否则是询问。
使用类 c++ 数组的书写方式，否则角标太复杂实在不好看。下文先讲二维再讲三维。
二维偏序
先对 x 维排序，再分治 y 维，每一次分治中点为 mid 的区间 [l,r)，我们都能保证，也必须保证 d[a].x\le d[b].x，a\in[l,mid)，b\in[mid,r)。
L=\{d[l],d[l+1],d[l+2],\dots \} \\
\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \uparrow \\
R=\{d[mid],d[mid+1],\dots \} \\
\!\! \uparrow
我们对两边同时向后处理（并非同步），我们正在处理 d[a] 与 d[b]，其中 d[a].id=-1 与 d[b].id\ne-1（其它情况不用考虑）。
如果 d[a].y\le d[b].y，由于分治，L 与 R 内以 y 为关键字肯定是有序的，所以 d[a'].y\le d[b'].y，a'\in[l,a]，b'\in[b,r]。
所以此时我们便可以记录 d[a] 的贡献（这里是 1），并将 d[a] 扔到归并排序的辅助数组里， a \leftarrow a+1。
同理，如果 d[a].y > d[b].y，我们直接由之前的贡献总和便可以计算答案，并将 d[b] 扔到归并排序的辅助数组里，b\leftarrow b+1。
三维偏序
进入正题，仿照上面的方法，在第一次 cdq 内部，每一层再执行另一种 cdq（cdq2），如果我们能保证 L 与 R 内部同时关于 x 与 y 有序就好了，可是我们在分治的过程中必然会将 x 打乱，如果有一种方法，能告诉我们 x 曾经在哪边，便能够解决这个问题。
也就是说：我们只想要曾经（x 维）在左边点的对右边询问的做贡献。
为此，我们扩展 d，加入一个名为 tag 的数据表示在当层是在左边还是右边，由于此时 y 早已有序，仿照二维进行 cdq2。
解释见代码吧，超详细的！
namespace PB {
node d[N]; // 存储当前处理的节点数组，包含点和查询
void solve(int l, int r) { // 处理区间 [l, r) 的 z 维偏序
if (l == r - 1) return;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid, r);
int a = l, b = mid, c = l, sum = 0; // sum 记录左边点的数量
while (a < mid || b < r) { // 归并排序，按 z 坐标合并
if (b == r || (a < mid && d[a].z <= d[b].z)) { // 左边还有元素且 z 更小（或右边已空）
if (d[a].id == -1 && d[a].tag == LEFT) // 如果是左边区间的一个点
++sum;
tp[c++] = d[a++];
} else { // 右边 z 更小（或左边已空）
if (d[b].id != -1 && d[b].tag == RIGHT) // 如果是右边区间的查询
anst[d[b].id] += sum; // 累加当前左边点的数量到查询结果
tp[c++] = d[b++];
}
}
copy(tp + l, tp + r, d + l); // 将临时数组复制回原数组，完成归并
}
} // namespace PB
namespace PA {
void solve(int l, int r) { // 处理区间 [l, r) 的 y 维偏序
if (l == r - 1) return;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid, r); // 递归处理左半区间 [l, mid) 和右半区间 [mid, r)
int a = l, b = mid, c = l; // a, b 分别指向左右区间，c 指向临时数组
while (a < mid || b < r) { // 归并排序，按 y 坐标合并
if (b == r || (a < mid && d[a].y <= d[b].y)) { // 左边还有元素且 y 更小（或右边已空）
d[a].tag = LEFT, tp[c++] = d[a++]; // 标记为左区间
} else { // 右边 y 更小（或左边已空）
d[b].tag = RIGHT, tp[c++] = d[b++]; // 标记为右区间
}
}
copy(tp + l, tp + r, d + l); // 将临时数组复制回原数组，完成 y 维归并
copy(tp + l, tp + r, PB::d + l); // 将排序后的数组复制到 PB 命名空间的 d 数组
PB::solve(l, r); // 调用 PB 处理 z 维偏序
}
} // namespace PA
时间复杂度
PB 中一次处理长度为 n 的区间 O(n)=n\log n。
PA（总）：O(\sum_{i=0}^{\log n}T(\frac{n}{2^i})\times 2^i) = O(n\log^2n) 。