2026 Summer Day3

课堂内容

CDQ 分治

还是用来解决偏序问题，通过分治和排序将偏序条件一层一层剥开，把多维偏序问题降唯达到求解问题的效果。

对于一些特殊的式子可以转化为偏序关系，然后用 CDQ 分治求解。

分块

主要就是回顾了一下对时间线分块，通过对时间线分块来处理修改和查询，使得暴力求解的复杂度与块的长度相关。

然后发现分块还要注意一下块长大小的选取，有时候需要通过计算获得最佳块长，不过大多数情况下为 $\sqrt{n}$。

莫队

大部分内容参见 莫队

这里主要补充一下莫队二次离线。

莫队二次离线问题主要处理的是那些看似可以使用莫队算法处理的结构，但是转移的复杂度并不是常数级别的。但是这类题目的答案往往具有差分类的性质，这时候就可以考虑使用莫队二次离线。

莫队二离通过预先处理询问的一些信息，将原本的区间询问 $[l, r]$ 拆分成两个单点询问 $l - 1$ 和 $r$，再通过预先求解的信息得到区间的答案。

例题如 P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II，发现每次转移的信息是询问当前新加入的数在原区间内有多少个数大于它，显然具有差分性质，所以可以使用莫队二次离线，先处理出 $f(i, x)$ 和 $g_(i, x)$ 表示在 $[1, i]$ 这个区间中有多少数大于/小于 $a_x$，然后后面莫队的转移复杂度就正确了。code

练习

P8253 [NOI Online 2022 提高组] 如何正确地排序

题目链接

这道题发现 $m$ 的范围很小，于是分类讨论 $m$ 的取值对应的做法有哪些。

• $m = 2$ 时，发现 $f(i, j) = \min(a_{1, i} + a_{1, j}, a_{2, i} + a_{2, j}) + \max(a_{1, i} + a_{1, j}, a_{2, i} + a_{2, j})$，这时候一定是一项取 $min$，另一项取 $max$ 的，所以 $f(i, j) = a_{1, i} + a_{1, j} + a_{2, i} + a_{2, j})$，直接统计即可。
• $m = 3$ 时，我们可以把 $min$ 和 $max$ 拆开统计，因为他们是互相独立的，这里只讨论 $max$ 的情况，即我们要求 $\displaystyle \sum_{a_{k, i} + a_{k, j} = \max(a_{t, i} + a_{t, j})} (a_{k, i} + a_{k, j})$，即如果把三维都写出来的话，就是要求满足 $t \neq k$ 的 $a_{k, i} + a_{k, j} \ge a_{t, i} + a_{t, j}$，移项得 $a_{k, i} - a_{t, i} \ge a_{t, j} - a_{k, j}$，所以就可以用二维偏序统计了。
• $m = 4$ 时，同 $m = 3$ 的情况转化即可。但是 题解给出了一种不一样的解法。我们考虑如果直接同上面统计的话是一个三维偏序问题，但是我们如果考虑反着做，如果所有 $(i, j)$ 均能够对答案产生贡献，那么就可以同 $m = 2$ 知道答案即为 $2n \times \sum_{i, j} a_{i, j}$，然后考虑我们多算的部分是什么，是那些满足 $a_{k_1, i} + a_{k_1, j} \le a_{k_2, i} + a_{k_2, j} \le a_{k_3, i} + a_{k_3, j}$ 的 $a_{k_2, i} + a_{k_2, j}$，我们同二处理后就是一个二维偏序问题，枚举 $k_1, k_2, k_3$ 就可以了。

code

P5443 [APIO2019] 桥梁

题目链接

这道题第一眼看过去以为是什么线段树分治 + Kruskal 重构树，但是发现 Kruskal 重构树的建树复杂度是 $O(n \log n)$ 的，套上线段树分治复杂度就是 $O(n^2 log^2 n)$ 的，无法接受。

然后就开始疯狂思考 Kruskal 重构树能否在原先的结构上完成题目的修改操作，实现动态更新，但是发现还是不可做。

后面又发现在边排序后，题目的要求其实是一个前缀的限制，然后开始考虑分块维护前缀并查集状态，发现空间不可接受且做法假了。

翻开题解发现，其实需要对操作和查询的时间线分块，和回滚莫队的思路有那么一点的相似，每次在块内处理询问之前的修改操作，然后暴力维护可撤销并查集即可。复杂度 $O(q \sqrt{q} \log n)$。

code