cdq，又一个大佬
CDQ分治
CDQ分治是一种运用广泛的分治思想，主要用于解决偏序问题，尤其是三维偏序，其主要思想是将区间分成两段，段内的信息递归处理，跨段的信息在左右两段都处理好后处理。
先看模板题吧：
三维偏序
这道题就是一个三维偏序的裸题，不过，在三维前，我们先想想一、二维偏序怎么做。
- 一维偏序
非常简单，排序即可，时间复杂度为 $O(n\log{n})$ - 二维偏序
先双关键字排序，完成后就可以不管第一关键字了（只需保证 $i>j$ 就可以使 $a_i \ge a_j$），而对于第二关键字，将其离散化到值域为 $[1,n]$ 建立一棵线段树来维护值 $x$ 的数量，则 $ask(1,1,b_i)$ 就储存了小于 $b_i$ 的值的个数，更新完 $i$ 的答案后让 $b_i$ 这个点 $+1$ 然后继续向后扫描即可。时间复杂度为 $O(n\log{n})$
如上，我们可以在 $O(n\log{n})$ 的时间内求解一、二维偏序，那么，我们现在来康康三维。
首先，类似一、二维偏序，三维偏序的第一维可以通过排序解决，第三维在前两维有序（即 $\forall i>j,a_i \ge a_j,b_i \ge b_j$ ）的情况下可以用线段树解决，问题在于：如何在保证前两维都有序？
很明显，在对第一维排序后（三关键字排序），若再更改顺序来满足第二维，第一维的单调会被破坏，而CDQ分治解决了这个问题，其过程如下：
- 对于区间 $[l,r]$ （此时第一维仍然单调）,把区间中满足三维偏序的数对 $(i,j)(i>j)$ 以 $mid$ 为界分为三种： $i,j \in [l,mid]$ 、 $i,j \in [mid+1,r]$ 、 $i \in [mid+1,r],j \in [l,mid]$
- 对于前两种（ $i,j$ 在同一段的）递归处理
- 处理完毕后，只剩下 $i,j$ 分别在 $mid$ 左右的情况，此时，由于 $mid$ 左边的数第一维一定小于右边，我们可以对左右分别以第二维排序，然后双指针枚举 $i,j$ 用线段树求解第三维
以上就是CDQ分治的主要思路，不难发现，由于每次取 $mid$ ，递归层数不会超过 $\log{n}$ 层，每一层中对左右的分别排序可以用归并在递归中顺带完成，真正消耗时间的是双指针和线段树，第 $x$ 层中 $[1,n]$ 被分为了 $2^{x-1}$ 段，每段时间复杂度为 $O(2^{x-1} \times \frac{n}{2^{x-1}} \times \log{ \frac{n}{2^{x-1}}}) = O(n\log{n})$ ，乘上层数，总时间复杂度为 $O(n \log^2_{}{n})$
一个要注意的问题是，当出现三维都相等的数时，会导致排在前面的数少算，故应先去重。
代码实现（注意代码中的 $m$ 是题目中的 $k$ ）：
1 |
|
应用
老C的任务
提示：考虑二维前缀和，对于每个询问 $(x1,y1,x2,y2),ans=s(x2,y2)-s(x2,y1-1)-s(x1-1,y2)+s(x1-1,y1-1)$ ，不妨以坐标作为第一、二维，是否是询问为第三维（是为1，不是为0）,把询问拆成四个点（注意保留符号），和不是询问的点一起，对于每个点，求其三维偏序（求出的点就是会对其二维前缀和有贡献的点），最后计算即可，本题第三维只有0、1两中情况，故可以省略线段树，直接用一个 $sum$ 记录为0的数的权值和。
代码：
1 |
|
动态逆序对
提示：以时间为第三维，对于每个删除，求出该删除会导致此时仍存在的数列减少多少个逆序对即可。注意第三维越大越早删除，注意逆序应分类讨论
代码：
1 |
|