CDQ分治是一种解决三维、四维偏序的算法。

三维偏序

三维偏序问题形如：

有 $q$ 次询问，每次询问有两种：

  • 修改：会给定 $t$、$x$、$y$、$v$，表示在时刻 $t$，在二维坐标 $(x,y)$ 上加上权值 $v$，修改会永久改变权值 （废话）。
  • 查询：会给定 $t$、$x$、$y$，表示求在时刻 $t$ 时，所有满足 $x’ \leq x$，$y’ \leq y$ 的二维坐标 $(x’,y’)$ 上的权值和。
  • $q \leq 2 \times 10^5$
  • $t,x,y \leq 2 \times 10^5$
  • $v \leq 10^9$

这种问题都有一个通用的解决方法，就是CDQ分治，接下来我们讲一下算法的原理。

我们先把所有的询问离线下来，然后按时刻（第一维）升序排序，显然排序前和排序后，相同询问答案不变。

接下来我们定义函数 $\text{solve}(l,r)$，代表只考虑 $l \sim r$ 内的修改，然后准确回答 $l \sim r$ 内的询问。

既然是分治，我们就要构建好整个分治思路，像这道题，就这样做：

  • 找到 $mid$ 为区间 $[l,r]$ 的中点 $\left\lfloor \dfrac{l+r}{2} \right\rfloor$。
  • 考虑 $l \sim mid$ 内的修改对 $l \sim mid$ 内的询问的影响：递归调用 $\text{solve}(l,mid)$。
  • 考虑 $mid+1 \sim r$ 内的修改对 $mid+1 \sim r$ 内的询问的影响：递归调用 $\text{solve}(mid+1,r)$。
  • 考虑 $l \sim mid$ 内的修改对 $mid+1 \sim r$ 内的询问的影响：
    • 把 $l \sim mid$ 内的修改，和 $mid+1 \sim r$ 内的询问，统统存入一个数组 $b$。
    • 把 $b$ 中所有元素按 $x$ 坐标（第二维）升序排序。

      有人对这一步的正确性有疑问，此处解释一下。

      我们初始时已经把所有询问按第一维排序了，所以一次询问 $i$（$i$ 为排序后的下标）只可能由（排序后的）下标比 $i$（严格）小的修改 $j$ 影响。

      我们统一假设询问、修改都是一起编号的，即我们把所有询问、修改放到一起，排序后，直接拿排序后的数组的下标作为编号。

      而我们已经指定了，$mid+1 \sim r$ 内的询问只能由 $l \sim mid$ 内的修改影响，所以就可以直接证明了。

      其实证明正确性的一种方式就是，证明排序前，一个询问 $i$，如果会受修改 $j$ 影响，那么在排序后，询问 $i$ 仍然会受修改 $j$ 影响（第一点）；反之，如果排序前，一个询问 $i$，不会受修改 $j$ 影响，那么在排序后，询问 $i$ 仍然不会受修改 $j$ 影响（第二点）。

      我们考虑，在排序后的数组 $b$ 中，对于任意的 $(i,j)$（$i>j$），都满足第二维的偏序关系；反之，对于任意的 $(i,j)$（$i<j$），都不满足第二维的偏序关系，即排序后的 $b$ 数组中，任意一个下标 $i$ 上的询问，都不能被下标 $j$（$j>i$）上的修改所影响。

      对应的，我们考虑在排序前的 $b$ 数组中，看看是否也不会被影响，显然是不会的，因为不管排序前后，第二维始终不满足偏序，也不会被影响。

      接下来考虑所有满足第二维偏序关系的 $(i,j)$（$i>j$），如果满足全部偏序关系，原本（排序前）是否也满足。

      也是显然的，因为如果 $i>j$，第一维偏序关系也满足，而在排序前也满足；第三维偏序关系也是一样的。

      同理也可以证明，所有满足第二维偏序关系的 $(i,j)$（$i>j$），如果不满足全部偏序关系，原本（排序前）也不满足。

    • 此时，第一、第二维全部都满足偏序了，所以我们就用树状数组维护第三维的偏序，然后从前往后依次考虑修改操作影响，并用树状数组回答询问，很好理解，也很好实现，此处略。

总复杂度：$O(q \log^2 q)$。

最后再说一下，如果上面题目中的 $t$ 代表的不是时刻，而是一维坐标，且不是先修改完再询问的特殊情况，那么上述做法会假掉，因为直接把第一维坐标排序会打乱修改和询问的次序，导致询问统计了不该统计的答案，需要用别的方式解决。

四维偏序

题目描述没差多远，不过这时候是三维坐标。

解法的话，我们先用CDQ分治将两维消除影响，然后还剩下两维需要单独维护。

此时，我们发现，我们又转化成了一个CDQ分治问题，所以再跑一遍CDQ分治即可。

所以，我们就解决了这题，用CDQ分治套CDQ分治。

用主定理可证明其复杂度为 $O(q \log^3 q)$。

有很多人都说，这CDQ套CDQ太难写了，其实四维偏序问题，只可能会在NOI及以上级别的考试中遇到，所以遇到概率特小，但掌握也是要的。

五维偏序

此时就要用到CDQ分治套CDQ分治套CDQ分治（

但此时复杂度就是 $O(q \log^4 q)$，已经接近 $O(q^2)$ 了，加上代码实现过于复杂，就需要另辟蹊径了。