三维偏序 -- cdq 套 cdq

似乎题解区并没有 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],… } ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣↑R={d[mid],d[mid+1],… } ⁣ ⁣↑ L=\{d[l],d[l+1],d[l+2],\dots \} \\ \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \uparrow \\ R=\{d[mid],d[mid+1],\dots \} \\ \!\! \uparrow L={d[l],d[l+1],d[l+2],…}↑R={d[mid],d[mid+1],…}↑
我们对两边同时向后处理（并非同步），我们正在处理 $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^{\prime }].y\le d[b^{\prime }].y$，$a^{\prime }\in [l,a]$，$b^{\prime }\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 PBnamespace 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 }^{2}n)$ 。