一些（可能？）有用的东西 & 思想和二级结论

· · 算法·理论

预计第一阶段写完投全站推荐大概 40KB。

计划每个大类下面分出来一些小类，防止找着麻烦。

会放一些相对冷门的算法和数据结构。

但是思想套路和 trick 会更多一点。

推一些东西Orz：

https://www.luogu.com/paste/8hnex65m

https://www.luogu.com/article/2buhtf2w

https://www.cnblogs.com/Zaunese/p/20230807--taolu.html

https://www.cnblogs.com/C202044zxy/p/15126199.html

集训队论文：

https://rusunoi.github.io/books/National-Team-Thesis/2021.pdf

https://rusunoi.github.io/books/National-Team-Thesis/年份.pdf

\textbf{ds}

对于这一部分，强烈推荐 UT 选集。

给定长度为 n 的两个序列 a,\,b，分别是颜色和权值。q 次询问修改，修改某个位置的颜色，某个位置的权值，或者查询 [l,\,r] 内 所有相同颜色的元素的权值和的 k 次方 的总和。n,\,q \le 5 \times 10^4,\,k \le 3。强制在线（tips：模拟赛时拼了两个暴力冲了 86pts/cf）。

while (N < q[i].l) sum = (sum * 2 % mod - C(N, M) + mod) % mod, ++N;
while (M > q[i].r) sum = (sum - C(N, M) + mod) % mod, --M;
while (N > q[i].l) --N, sum = (sum + C(N, M)) % mod * iv[2] % mod;
while (M < q[i].r) ++M, sum = (sum + C(N, M) + mod) % mod;

rldcot 支配： 对于一个点，它成为 LCA 被贡献，考虑重子树中某个点 x，一定是选取 LCA 轻子树内 x 的前驱或者后继。

由于这样的前驱和后继数量不会超过轻子树大小，总的可能的点对数量不超过 \Theta(n \log n) 个。

一个小 trick 是对于 [l,\,r] 找到某个合法点并且递归下去的题，可以从左右开始向内收缩找。时间复杂度 T(n) = T(x) + T(n - x) + \min(x,\,n - x) = \Theta(n \log n)。比如最值分治（等价于在笛卡尔树上启发式分裂）。P4755。

树上启发式分裂能干的事情，大部分时候带撤销线段树合并也可以干。九省联考 希望。

我认为它们本质相同。

tips：fhq-Treap 也可以做到均摊 \Theta(n \log n) 的启发式合并，link。

双指针做删除麻烦的时候可以考虑（比如最值）。

基础的双指针是直接维护 [l,\,r] 的合法性，然后向右移动 r 并根据区间合法性向右移动 l。

如果困难删除，但是合并容易做到，那么可以考虑不带删尺取。

考虑类似猫树的思想，维护 \text{mid}，钦定区间经过 \text{mid}，那直接维护 \text{mid} 结尾的后缀信息并即可，g_l \leftarrow f(l,\,\text{mid})。

如果 $l > \text{mid}$，则 $\text{mid} \leftarrow r$，暴力重构 $g$ 即可，暴力重构时 $l$ 不会低于原来的 $\text{mid}$，$r,\,\text{mid}$ 单调不减。时间复杂度 $\Theta(n)$。 [CF1548B](https://www.luogu.com.cn/problem/CF1548B)。 由此可以将 WC2024 T2 水镜优化到线性。 拓展的话，这玩意本质是双栈维护双端队列，你可以每次在左栈空的时候给右栈劈出来一半分别为左右栈。 - **欧拉序维护树的直径**：[CF1192B](https://www.luogu.com.cn/problem/CF1192B)。 - **超级钢琴 trick**：[评价是 lsj 爆杀我无数条街Orz](https://www.luogu.com.cn/article/6i7m4hr6)。 - $a < b < c$ 则 $\min(a \oplus b,\,b \oplus c) < a \oplus c$。对于最大化 $\text{and}$ 或最小化 $\text{or}$ 有类似结论，但是要求往后 $\log$ 个的 $\max/\min$。 tips：区间本质不同 gcd 数，lcm 数，or 数，and 数都是 $n \log v$ 级别的。ST 表预处理 gcd 的复杂度是 $\Theta(n \times (\log n + \log v))$ 的。 - 选出子集大小对于 $n$ 的占比较大，最优化问题，考虑随机一个数是子集的代表元。[CF364D](https://www.luogu.com.cn/problem/CF364D)。 - $\sum x_i = n$，则本质不同 $x_i$ 数量只有 $\Theta(\sqrt n)$ 个。 - **折半警报器**：给定簇和对应权值，每次将包含一个点的所有簇的权值减少 $v$，求某个簇被减到 $< 0$ 的最早时刻。 鸽巢原理：$\left(\sum_{i = 1}^{n} a_i\right) \ge k \Rightarrow \max a \ge \lceil \frac{k}{n} \rceil$。 于是当簇内出现新的 $\max a \ge \lceil \frac{k}{n} \rceil$ 才值得我们去查看一次，把这个设计为阈值。如果出现了就让簇的权值加上所有减量，更新阈值即可，假警报的次数是 $\log$ 级别的。[P7603](https://www.luogu.com.cn/problem/P7603)。 **Promax**：[二进制警报器](https://www.luogu.com.cn/article/gz6wr8e3)。 - **三维偏序 $\Theta(n \log n)$（只能求总量）**：考虑容斥，https://www.cnblogs.com/YunQianQwQ/p/16364951.html - 区间 chkmax 区间加法的 **segbeats（吉司机线段树） 的复杂度：已经被确认是 $\Theta(n \log^2 n)$ 的**，来自 Tony2 老师的斐波那契构造。 - **KTT**：维护一次函数区间加最值的数据结构。[P5073](https://www.luogu.com.cn/problem/P5073)，[感觉很牛的博客](https://www.cnblogs.com/cndarkmoon/articles/18216427)。 - **分散层叠**：加速 $k$ 个长度为 $n$ 的序列的二分。https://www.luogu.com.cn/article/dswvjs1j。 - 线段树的 $\text{pushup}$ 复杂度是关于区间长度的根号，整体复杂度也是 $\Theta(n \sqrt n)$ 的。[文化课](https://www.luogu.com.cn/problem/P5608)。 $\textbf{Winter Camp}

https://blog.mhxma.tech/2024/02/08/xuexibiji-chijiuhua/

使用重量平衡树维护，根对应 [0,\,2^w - 1]，左右儿子分别是 [l,\,\text{mid}] 和 [\text{mid},\,r]，比较大小直接比较 \text{mid}。

【模板】后缀平衡树。

整个 WC2024 第一课堂只听懂了数据结构开头的几个部分。

upd：已经有数据卡掉了，可以宣布这种写法 SPFA 了。

可以写 WBLT 做到复杂度严格正确的可合并持久化。

图论

  1. 所有点到重心的距离和是最小的，跟点权和边权无关。

  2. 合并两棵树，新的重心在原来两棵树的重心在新树的连线上。P4299。

  3. 增加一个叶子，重心至多移动一步。

  4. 任意根，任意 dfs 序排行一半的结点祖先链中一定包含重心，如果难以维护 dfs 序，则随机一个点，有一半的概率祖先链包含重心。

  1. 直径中点是到其它结点最大距离最小的点，且所有直径都交于这个点。

  2. 到结点 u 距离最大的点一定是直径端点。

根据上面的结论，到点 u 距离最大的路径一定过直径中点。

  1. 直径的封闭性：两个树直径分别是 a,\,b 和 c,\,d，合并后的直径还是在 a,\,b,\,c,\,d 中选择。

  2. 推一个感觉很牛的博客。

\max_{l \le l' \le r' \le r \wedge r' - l' + 1 \ge k} d_{\text{lca}(l',\,l'+1,\,\dots,\,r')} = \max_{l \le l' \le r' \le r \wedge r' - l' + 1 \ge k} \min\{ d_{\text{lca}(l',\,l'+1)},\,d_{\text{lca}(l'+1,\,l'+2)},\,\dots,\,d_{\text{lca}(r' - 1,\,r')}\}

NOIP2024 T4 树上查询。

\text{lca}(a_1,\,a_2,\,\dots,\,a_k) = \text{lca}(\text{mindfn}(a),\,\text{maxdfn}(a))

dfs 序和按 dfs 序排序后的相邻点的 lca 构成了虚树的所有点。

包含 a_1,\,\dots,\,a_k 的最小联通块大小：

树上连续的 dfs 序区间 [l,\,r]，并上 l - 1 对应结点到根的路径，是一个连通块。U625762 红蓝树。

d_{\text{lca}(a_1,\,a_2)} + d_{\text{lca}(a_2,\,a_3)} + ,\, \dots ,\, + d_{\text{lca}(a_{k - 1},\,a_k)} - d_{\text{lca}(a_1,\,a_2,\,\dots,\,a_k)}

如果把第一个点和最后一个点也看作相邻的话，那么就不需要减最后的总 lca 深度，答案就是总和除以二再减一。JOISC2023 Day3 Tourism。

动态 Top Tree 似乎在 OI 里是没有什么应用场景的。

但基于全局平衡二叉树，有简单构建静态 Top Tree 的方法，对于维护树形态极其强力。

https://www.cnblogs.com/ExplodingKonjac/p/17890636.html

旅行者那道题的非随机化做法，有一个类似的但更牛的东西。CF1365G，我叫它 13 选 6 trick。

所以只要我们的信息可差分就能做，比如我们可以直接让点权为 i - fa_i 做到查询 [l,\,r] 对 x 的 LCA 编号和。

剖分方法：从 1 开始，设当前是 u，先给 u 标号（如果 u 没有标号），如果 u 是重链顶则在重链上给所有重链挂着的轻儿子标号，然后递归重儿子再递归轻儿子。

时间复杂度与重剖相同。

知道了这个可以轻松切 NOI2021 轻重边。

每次跳轻边，要么 f 减半，要么 g 翻倍。

维护 SAM 这种路径数有限的 DAG 极其强力。Border 的四种求法。

经典题：Xor MST。

Tree MST：将原图分成两个部分，分别做最小生成树，保留各自最小生成树的边集，并起来再做一遍最小生成树，一定是原图的最小生成树。

于是可以分治计算最小生成树。

- **竞赛图的性质**：竞赛图缩点后成为一条链，[其它性质](https://www.cnblogs.com/acha/p/9042984.html)。 ### 字符串 - **一些经典结论** 广为人知的**弱周期引理**：$x,\,y$ 是 $s$ 的周期且 $x + y \le |s|$，则 $\gcd(x,\,y)$ 是 $s$ 的周期。 证明考虑证明 $x < y,\,y - x$ 是周期（这显然易证），施更相减损术。 由此我们可以推出所有周期都是最小周期的倍数。 有推广，**周期引理**：$x,\,y$ 是 $s$ 的周期，且 $x + y - \gcd(x,\,y) \le |s|$，则 $\gcd(x,\,y)$ 是 $s$ 的周期。 更广为人知的：**$s$ 的任何长度 $\ge \lceil\frac{|s|}{2}\rceil$ 的 border 形成等差数列。** 所以 border 是 $\log$ 段等差数列。 以及长度在 **$[2^{i - 1},\,2^i)$** 内的 border 形成等差数列（就是按最高位分组）。 公差 $\ge d$ 的 border 等差数列总大小是 $\Theta(\frac{n}{d})$ 级别的。 似乎失配树缩最小编号的儿子的链后，树高不超过 $\Theta(\log n)$。[link](https://www.luogu.com/article/lg6oo4s3)。 [调查：你能求出这份代码跟正解的最小编辑距离吗？](https://www.luogu.com.cn/article/6di9cc0v) 所以令 $d \leftarrow x - \text{nxt}_x$，我们每次可以直接跳到 $x \leftarrow x - \lfloor\frac{x}{2d}\rfloor \times d$ 位置，做到失配树上的快速跳跃。这样做的好处是动态加字符很方便，而且不需要额外空间。 - 对于构造最小化字典序的问题，以不计代价最小化最前面为导向。 - > $\sum x_i = n$，本质不同 $x_i$ 最多只有 $\Theta(\sqrt n)$ 个（这个性质真的很多题都用到过）。 将 $x_i$ 看作长度，那么一类给定多个模式串，在文本串上匹配计算贡献的问题，经常存在暴力 hash 的 $\Theta(n \sqrt n)$ 做法。[Mike and Friends](https://www.luogu.com.cn/problem/CF547E)。 - **广义 SAM 的小常数正确写法**： 添加特殊字符，一般（如果不需要区分不同字符串就不需要）需要将字符集开到很大，保证能区分不同字符串。字符串开大，我们将不得不使用平衡树和哈希表等维护 SAM 的转移边。导致时空常数升天。 每次将 $\text{lst}$ 置为 $1$，则复杂度正确，一般情况下问题也不大。但是会产生空结点导致 $\text{parent tree}$ 的 $\text{siz}$ 计算出错等问题。 https://www.cnblogs.com/ying-xue/p/general-sam.html - SAM 结点按 $\text{len}$ 的升序排序就是拓扑序，不需要建出图之后再跑一遍拓扑排序。 - **Hash Killer III**：自然溢出和单模小模数 hash 都被卡烂了，然后实际上固定 base 多模 hash 也是可以被卡的。 https://www.luogu.com/article/fx07jjaz 当然如果随机 base，目前应该是找不到稳定方法卡掉的。 ### 数学 - **随机游走**：直线和平面上的随机游走，我们都有结论，如果从原点开始走 $n$ 步，期望下跟原点距离是 $\Theta(\sqrt n)$ 级别的，而且它们都是**常返**的，**三维空间以上的随机游走没有这个结论。**[混乱邪恶](https://www.luogu.com.cn/problem/P7606)。 - **拆贡献技巧**：$x$ 的期望 $\to$ 枚举 $x$，算 $x$ 的出现次数/概率。$f(x = k) \Rightarrow$ $f (x \ge k) - f(x \ge k + 1)$。 $$ E(X) = \sum_{i = 0}^{+\infty} P(X = i)i = \sum_{i = 0}^{+\infty} \sum_{j = i}^{+\infty} P(X = j) = \sum_{i = 0}^{+\infty} P(X \ge i) $$ - **Kth Min-Max 容斥**： $$ \begin{aligned} \text{kthmax}(S) = \sum_{T \in S}(-1)^{|T| - k}\binom{|T| - 1}{k - 1} \min(T) \\ \text{kthmin}(S) = \sum_{T \in S}(-1)^{|T| - k}\binom{|T| - 1}{k - 1} \max(T) \end{aligned} $$ [重返现世](https://www.luogu.com.cn/problem/P4707)。 - 本质不同前后缀最值数期望是调和级数。 - $ab = \dbinom{a + b}{2} - \dbinom{a}{2} - \dbinom{b}{2}$，作用就是用来把 $ab$ 拆成 $a + b,\,a,\,b$ 的量。在 $a + b$ 是定值的时候非常有用。[有标号 DAG 计数](https://www.luogu.com.cn/problem/P6295)。 - 线性基性质更好的建立方法： ```cpp for (auto& i : b) x = min(x, i ^ x); for (auto& i : b) i = min(i, i ^ x); if (x) b.push_back(x); ``` 这种建立方法所有数异或起来就是异或最大值（似乎跟高斯消元建法的性质一样）。 一般的建法不保证这个，性质差点。 对于不定方程 $ax + by = c,\,\gcd(a,\,b) = 1$，有**正整数解**的充分不必要条件是 $c > ab$。[ABC306G](https://www.luogu.com.cn/problem/AT_abc306_g)。 ### $\textbf{dp}

https://www.luogu.com.cn/article/ki71nw88

\begin{aligned} & f_{i,\,j} \gets f_{i - 1,\,j} \times a_i + f_{i,\,j - 1} \times b_i \\ & \text{delete k:}\\ & f_{i - 1,\,j} \gets \frac{f_{i,\,j} - f_{i - 1,\,j - 1} \times a_k}{b_k} \end{aligned}

Alex-Wei 同余最短路的转圈技巧。

贪心，随机化和 \textbf{ Ad-hoc}

『EX』卡常

矩阵乘法可以写成：

rep(i, 1, n) rep(k, 1, n) rep(j, 1, n)

原因是内存访问连续了。

同理 ST 表 \log 那维开到第一维会更好。

x += y; while (x >= mod) x -= mod; 似乎比 x += y; if (x >= mod) x -= mod; 更快。

先咕一下。

一些经典复杂度不可优化题

经典例子如 SAT（有 SETH 这种东西） 和大部分背包问题，整数规划。

一些不那么广为人知的：

  1. 用若干不相交的三元组恰好覆盖所有点/最多能选出多少三元组。

  2. SVP（若干平面向量，非零整数倍线性组合到原点最小距离），CVP（原点改为任意点）。

  3. 积和式（规约二分图完美匹配计数，因此排列计数题想二分图多半不行）。

这个不知道是否 NPC，但没有已知多项式算法。

  1. LCS：|\Sigma| = \Theta(1),\,\Theta(\frac{n^2}{\log^2n})。

  3. OV（给两组向量，长度均 \Theta(\log n)，问是否存在 a_i 和 b_j 正交）：如果 SETH 成立，则至少 n^{2 - o(1)}。

  4. 3SUM 问题（三个集合，问是否能各自选出三个数总和为 0）。三点共线，三线共点，三等差数列，3XOR。