洛谷秋令营Day1-进阶算法思想

单调数据结构

CF547B，经典单调栈，求出 a[i] 支配区间的长度为 len，则 [1, len] 的长度的最小值的最大值都至少为 a[i]，这个使用后缀 max 就可以维护，当然也可以使用线段树 beats，但纯属小题大做了。

CF1407D，按照 h[i] 和 h[j] 的大小分类讨论

ABC352D，考虑数字 i 出现的位置是 q[i]，则考虑数字 [i, i + k - 1] 的位置们能不能满足题意。能的话，就是求 max(q[i...i + k - 1]) - min(q[i...i + k - 1])

CF1195E，形状是 a * b 是固定的，所以我们求一下每行每 b 个数的 min，接着对这些 min，再求每列每 a 个数的 min 就好了

主要是贪心的证明，看交换会让答案更差的话，应该满足什么样的条件。

P1080，考虑某个顺序是最优的，考虑相邻的两个数 i 和 j，分别写出这两个东西的值，再看看交换成 (j, i) 之后，这两个东西的值，从而转化成 max() < max() 的形式。

CF1552E，考虑 n / (k - 1) 上取整是什么意思，发现假如每 k - 1 种颜色分一组，每组内选的区间互不相交，则至多分 n / (k - 1) 组，覆盖次数也符合题意（需要证明）。

跳步型倍增，拆分型倍增

CF1142B，预处理每个 a[i] 的下一个数是谁，并预处理 i 往后跳 2^j 跳到哪里，这样可以枚举第一个数是谁，看一下跳 n - 1 步跳到了哪里。

CF932D，如果没有加叶子的操作，其实就是相当于每个点要求上面第一个比自己大的点（倍增+二分求），把这个东西建一个新的树，在这上面再倍增跳，看看跳多少会爆和的范围，就知道最多能跳多少步了。

CF1848F，先打表找一下变换的规律，可以发现经过 2^k 变换之后的结果很干净。并且由于 n = 2^k，所以始终是能变成 0 的。我们二分变换次数，然后拼凑出这个次数的每个位置变换的结果，看看是不是全 0 就好了。

序列分治、矩形分治、树形分治

CDQ 分治：序列劈成两半，只在左边或者右边的对递归下去处理，跨区间的点对使用数据结构快速统计。有可能需要对序列做修改，所以要先递归下去做完，再对序列做修改，处理本层跨区间的问题。归并排序就可以看成一种 CDQ 分治。

n 维静态偏序问题 = n - 1 维动态偏序问题。

三维偏序：

CDQ 分治优化 DP，先把 [l, mid] 的 DP 值求出来，再计算 dp[l...mid] 对 dp[mid + 1...r] 的贡献，再做 dp[mid + 1...r]。P4093

对于可持久化数据结构，可以在时间轴上进行分治。后边不会了，也超过了 S 组难度。

撤销的复杂度一般小于删除的复杂度。

严格、期望、均摊复杂度，严格和期望可以撤销，均摊一般不能撤销，因为可能撤销每次都是 O(n)。

树分治：找到重心，每个连通块内部的各自处理，然后跨连通块的是经过重心的，用另一种处理方法。

如何求重心？先预处理所有子树大小，然后枚举点，看最大子树以及剩余部分的大小即可。

4 点 45 之后的内容基本上不用掌握了。

CF914E