MY OI

NOI2020 加油！！！

NOI2014~2019 题目分析

题目类型

比赛

模板

• 在不必要的情况下不写 IO 优化，直接用 scanf 和 printf。
• 前面的 define 用时再打，没必要先打好。
• modint 如果有必要可以简略地写一下，用起来还是挺省时间的。

对拍

• 测试键盘和鼠标时就打对拍的程序，因为无论如何都要用。
• 随机数生成就随两个数移 $31$ 位异或起来构成 ll，然后再取模，写两个函数就可以了，记得一定要 srand(time(0))。
• 无论什么题目，先打暴力，之后一定要对拍，但也不能太过保守。

卡常

• 循环展开有时候很有用，但不到万不得已不要用。

Trick

• 比赛时间是 $5\text{h}$，也就是 $300\text{min}$，而题目总分是 $300$ 分，所以如果估计的使用时间比得分大太多，应该扔了。
• 两天的第一题都尽可能要 AC，其它题要拿个至少 $40$ 分，这样总分就是 $5+100+100+40+40+100+40+40=465$，这个分数足够前 $100$ 了，再多拿点就可以进集训队了。
• 该拼部分分拼部分分，即使过了拍也最好写一下数据分治，也可以根据部分分剪剪枝，免得正解挂了部分分都拿不到。
• 空间大小一定要算清楚，既要避免用 STL 炸空间，又一定一定要开足。
• 要特别注意明显过小的数据范围，那很可能是突破口。
• 没思路时打表找找规律。

贪心

• 带悔贪心两个方法：
  • 算上反悔的代价之后用堆贪心。
  • 模拟费用流，其实也就是建出费用流的图然后利用图的特殊性质模拟跑。
• 最优化问题想想二分答案，比如 $0/1$ 分数规划。
• Huffman 树：要求 $(n-1) \bmod (k-1) = 0$，$n$ 不足先扩充 $0$，然后用堆实现。
• 正序不行考虑倒序，可能会简单很多。
• 价值为 $2^i$ 且两两不同的直接贪心。
• 字典序相关的直接贪心。
• 贡献长成 $\sum_{i=1}^n ia_i$ 这样子的，按平均数从大到小贪心。
• 大胆猜结论，然后对拍验证。

动态规划

• 指数级大暴力通常都可以优化成 DP，想清楚状态中需要记录哪些信息就好了。

状态

• 状态数远大于答案数的时候，考虑将状态和答案交换，将答案写进状态。
• 合法状态不满的时候可以考虑记忆化搜索，不用记搜也要尽可能的剪枝，说不定可以降复杂度，降不了也可以减小常数。
• 可以滚动数组的时候就滚动一下，不仅减小空间还减小常数（高维数组寻址常数很大）。

背包

• 多重背包考虑二进制拆分。

区间 DP

• 以大小为阶段的区间 DP 考虑笛卡尔树优化。

树形 DP

• $f_{1\dots n,1\dots k}$ 的树形背包复杂度是 $\mathcal O(nk)$ 的。
• 根不确定的树形 DP 考虑换根 DP。

动态 DP

• 树上带修的 DP。
• 核心思想就是每个点维护一个状态矩阵，对树进行树链剖分，使得每一条重链的顶端的状态矩阵，就是这条链上的状态矩阵根据广义矩阵乘法合并后形成的矩阵。
• 然后用线段树维护这些状态矩阵，这样每次修改都只会修改 $\mathcal O(\log n)$ 个位置的值，单次修改的复杂度为 $\mathcal O(\log^2 n)$。

数位 DP

• 基本上都需要差分容斥。
• 由于转移比较固定，可能可以矩阵乘法优化。

前缀和/差分优化

• 虽然简单但实用。
• 一类题目为要求序列 $a$ 的方案数，限制为 $a_i \in [l_i,r_i]$，还有一些其它的限制。通常可以对 $[l_i,r_i]$ 进行区间离散化，对于每一段区间的转移都是类似的，可以快速处理，一般会配合前缀和优化。

环形

• 断环成链，比如基环树 $\to$ 树。

矩阵加速

• 如果是 $0/1$ 矩阵则考虑 bitset，特别是图上走 $k$ 步这样的问题，复杂度可以做到 $\mathcal O(\frac{n^3\log k}w)$。

数据结构优化

• 想清楚每次进行的操作是什么，转化成数据结构问题。

斜率优化

• 斜率优化的主要形式还是因题而异，上凸壳下凸壳切点等等都有可能。

决策单调性

• 决策单调性就不要证了，大胆猜然后打表。
• 方法有两个：
  • 建一个队列，里面保存三元组 $(l,r,x)$，表示当前情况下 $l \sim r$ 的最优决策在 $x$。
  • 当考虑到 $i$ 时：
    1. 若队头的 $r < i$，则弹出队头。
    2. 用此时的队头作为最优决策转移到 $i$。
    3. 不断弹出比 $i$ 更劣的队尾。
    4. 若此时队尾比 $i$ 优，则直接将 $i$ 补在队尾。
    5. 否则在队尾上二分找到第一个以 $i$ 为最优决策点的位置，改变队尾的 $r$ 值，同时插入 $i$。
  • 时间复杂度 $\mathcal O(n \log n)$。
• 上面这个方法适用于能够快速计算转移值 $w_{i,j}$ 的时候，当不能快速计算但 $w_{i,j}$ 可以类似莫队那样快速增减一个数时，通常采用下面这种类似整体二分的方法（当然这种方法在能够快速计算 $w_{i,j}$ 的值时显然也是有效的）：
  • 题意：已知 $g_{0\dots n-1}$，要求 $f_{1\dots n}$，其中 $f_i = \min_{k=0}^{i-1} (g_k + w_{k+1,i})$，且 $g \to f$ 的转移具有决策单调性。
  • 设问题 $(l,r,L,R)$ 表示要求 $f_{l\dots r}$，决策点在 $[L,R]$ 中，则一开始我们需要计算的问题为 $(1,n,0,n-1)$。
  • 对于问题 $(l,r,L,R)$，设 $d = \lfloor\frac {l + r}2 \rfloor$，如果我们求出了 $f_d$ 的决策点为 $k$，则 $f_{l\dots d-1}$ 的决策点在 $[L,k]$ 中，$f_{d+1\dots r}$ 的决策点在 $[k,R]$ 中，于是变成两个子问题 $(l,d-1,L,k)$ 和 $(d+1,r,k,R)$。
  • 考虑如何计算 $w_{l,r}$，类似莫队的方式暴力移动左右指针即可，分析一下左右指针的移动次数会发现都是 $\mathcal O(n \log n)$ 的。
  • 时间复杂度 $\mathcal O(n \log n)$。
  • 若是 $f \to f$ 而不是 $g \to f$，则还需要套一层 CDQ 分治。

WQS 二分

• 在最优化问题中出现「恰好」考虑 wqs 二分。
• 比如求恰好 $k$ 个情况下的最大值。
• 设 $k$ 的答案为 $f(k)$，首先我们找到没有 $k$ 限制的最大值 $f(x_0)$。
• 然而恰好 $x_0 = k$ 几乎不可能，如果 $f(x)$ 是上凸的，则设 $g(x) = cx + f(x_0)$，则 $x_0$ 显然为 $c=0$ 时 $g(x)$ 与 $f(x)$ 的切点（即最大值）。
• 那么如果找到使得 $x_0 = k$ 恰好为切点的 $c$，即可求出 $f(k)$ 的值。
• 由于 $f(x)$ 是上凸的，因此当 $c$ 变大时切点 $x_0$ 变小，$c$ 变小时切点 $x_0$ 变大，具有单调性，因此可以在 $(-\infty, \infty)$ 之间二分 $c$。
• 最后的问题是在对于一个 $c$，我们如何求出切点 $x_0$，也就是最大值。
• 考虑 $g(x) = cx + f(x_0)$ 的意义，相当于 DP 时每多选一个就要把权值加上一个 $c$，这可以直接添加到 DP 的实现中去。

字符串

Hash

• 字符串首先还是考虑 Hash，注意要稍微估一下错误率，必要时写双 Hash，随机 $\mathrm{base}$，随机 $\bmod$。
• 复杂度卡得不紧错误率不高就直接 map，否则可以写一下邻接表。

AC 自动机

• AC 自动机上可以跑 DP。

SA

• 基本上把 SA 求出来之后就是另一道题了。

数论

• $w(n)$ 和 $d(n)$ 都蛮小的，一般前者都可以指数算法，后者都可以多项式算法。

基本算法

• gcd，exgcd。
• crt，excrt。
• bsgs，exbsgs。

调和级数

• 调和级数 $\mathcal O(\sum_{i=1}^n \frac{n}{i}) = \mathcal O(n \log n)$。

数论分块

• 数论分块：整除的结果只有 $\mathcal O(\sqrt n)$ 个。

Lucas 定理

• 模数小时用，$\binom{n}{m} \bmod p = \binom {\lfloor \frac {n}{p} \rfloor}{\lfloor \frac {m}{p} \rfloor} \binom{n \bmod p}{m \bmod p} \bmod p$。

莫比乌斯反演

• 若 $f(n) = \sum_{d|n} g(d)$，则 $g(n) = \sum_{d|n}\mu(\frac nd)f(d)$。
• 若 $f(d) = \sum_{d|n} g(n)$，则 $g(d) = \sum_{d|n} \mu(\frac nd) f(n)$。
• $\mu * \mathbf{1} = \epsilon$，$\varphi * \mathbf{1} = \mathbf{id}$，$\mu * \mathbf{id} = \varphi$。
• $d(ij) = \sum_{x|i}\sum_{y|j}[x\perp y]$，可以扩展到多项。

杜教筛

• 设要求 $f$ 的前缀和 $S_f$，构造另一个积性函数 $g$，令 $f * g = h$，则有 $S_f(n) = \frac{S_h(n) - \sum_{i=2}^n g(i) S_f(\lfloor \frac ni \rfloor)}{g(1)}$（可以现场手推），因此要求能够快速求 $S_g,S_h$。
• 对于 $x \le n^{\frac 23}$ 的 $S_f(x)$ 进行线性筛，$x > n^\frac 23$ 的 $S_f(x)$ 进行杜教筛时，杜教筛的复杂度达到最优的 $\mathcal O(n^{\frac 23})$。
• 记忆化搜索时，我们需要存下 $S_f$。对于线性筛的部分显然不用存了，剩下的部分将 $f(x)$ 存入 $\lfloor \frac n x \rfloor$ 的位置，在单组数据时不会造成冲突。

原根

• 若 $g$ 在 $\bmod m$ 下的幂的循环为 $\varphi(m)$，则称 $g$ 为 $m$ 的原根。
• 若 $g$ 是 $m$ 的原根，当且仅当 $\gcd(g,m) = 1$，且对于 $\varphi(m)$ 的任意一个质因子 $p$，都有 $g^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m$，利用这个可以快速找到一个原根。
• 若 $p$ 为质数，则 $g^{0\dots p-2} \bmod p$ 恰好覆盖 $[1,p-1]$ 各一次。
• 原根通常比较小。

同余最短路

• 给定 $a$，求 $\sum_{i=1}^n a_ix_i$ 的值在 $\in[0,m]$ 中有多少个数有解。
• 拿一个 $a_i$ 出来当模数，建 $a_i$ 个点，编号为 $0 \sim a_i - 1$。
• 将其它的 $a_i$ 作为有向边，求出点 $p$ 的最短路，表示最小能到达的 $\bmod p$ 的值。

多项式

拉格朗日插值

• 过 $n$ 个点的多项式为 $f(x) = \sum_{i=1}^n\left(y_i\prod_{i \ne j} \frac{x-x_j}{x_i-x_j}\right)$，可以 $\mathcal O(n^2)$ 求 $f(k)$ 和多项式本身。
• 当 $x_i = i$ 或 $x_i = i-1$ 时可以 $\mathcal O(n)$ 求 $f(k)$，但多项式本身还是得 $\mathcal (n^2)$。

NTT

• 可以处理带通配符的字符串匹配：
  • 两个长度为 $n$ 的字符串 $a, b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2 = 0$。
  • 如果带有通配符，将通配符看成 $0$，则 $a,b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2a_ib_i = 0$。
  • 套路地将 $a$ 串翻转，最后即为三个卷积，可以 NTT。

FWT

• $\mathrm{or}$ 是小 $\to$ 大，$\mathrm{and}$ 是大 $\to$ 小，$\mathrm{xor}$ 是 $\times$ 系数后加减。
• 子集卷积就是 $\mathrm{xor}$，然后数组多加一维表示子集大小。
• 异或卷积 $A \operatorname{xor} B = C$ 中，知道 $C$ 和 $A/B$ 中的一个，也可以求出另一个，将中间的乘法改成除法即可。注意方程可能有通解。

组合计数

• 用怎样怎样的方法生成一个序列/字符串/矩阵之类的，问能生成多少个本质不同的东西，一般找合法的判定方法，然后对着这个方法 DP/容斥/推公式。

隔板法

• $n$ 个一样的小球放入 $m$ 个不同的盒子中方案数为 $\binom{n+m-1}{m-1}$。

二项式定理

• $(x+y)^n = \sum_{k=0}^n \binom nk x^ky^{n-k}$，可以扩展到多项。

抽屉原理

• 有时候会有妙妙用。

概率期望

• 利用线性性拆贡献。
• 经典模型：有 $n$ 个点，$i$ 有 $p_{i,j}$ 的概率通向 $j$，求从 $s$ 开始期望多少步第一次到达 $t$。
  • 通常的做法是设 $f_i$ 表示从 $i \to t$ 的期望步数，则有转移：$f_{i} = 1+ \sum_{j} p_{i,j}f_j$，边界为 $f_t = 0$。
  • 如果这张图是 DAG，则根据上面的转移可以做到 $\mathcal O(n+m)$ 求出所有 $f_i$。
  • 如果不是 DAG，则要解一个 $n$ 元 $n$ 次方程组，使用高斯消元，时间复杂度为 $\mathcal O(n^3)$，如果高斯消元的系数具有一定的特殊性，可能可以更优。
• 有的时候方案数转成概率会容易很多。

$\text{Fibonacci}$ 数

• $\gcd(F_n, F_m) = F_{\gcd(n,m)}$。
• $\sum_{i=0}^n F_i = F_{n+2}-1$。
• $\text{Fibonacci}$ 数列模 $m$ 意义下循环节长度 $\le 6m$。

$\text{Catalan}$ 数

• 递推公式：$C_{n} = \sum_{i=0}^{n-1} C_{i}C_{n-1-i}$，边界为 $C_0 = 1$。
• 通项公式：$C_{n} = \binom {2n}{n} - \binom {2n}{n-1} = \frac{\binom{2n}{n}}{n+1} = \frac{C_{n-1}(4n-2)}{n+1}$。
• 要求从 $(0,0)$ 走到 $(n,m)$ 且不能碰到 $y=x+k$ 的方案数，在方案数不为 $0$ 的前提下，考虑所有碰到 $y=x+k$ 的折线，翻转从 $(0,0)$ 到第一次碰到 $y=x+k$ 这部分，那么每条不合法的路径一一对应了从 $(-k,k)$ 走到 $(n,m)$ 的一条路径，因此方案数为 $\binom{n +m}{n} - \binom{n+m}{n+k}$。

第一类 $\text{Stirling}$ 数

• 意义：$S_1(n,m)$ 表示 $n$ 个元素构成恰好 $m$ 个圆排列的方案数。
• 递推公式：$S_1(n,m) = S_1(n-1,m-1)+(n-1) \cdot S_1(n-1,m)$。
• $n! = \sum_{i=0}^n S_1(n,i)$。
• 下降幂 $\to$ 常幂：$x^{\underline{n}}=\sum_{i=0}^{n}(-1)^{n-i} S_1(n, i) x^{i}$。

第二类 $\text{Stirling}$ 数

• 意义：$S_2(n,m)$ 表示 $n$ 个元素构成恰好 $m$ 个非空集合的方案数。
• 递推公式：$S_2(n,m) = S_2(n-1,m-1) + m \cdot S_2(n-1,m)$。
• 通项公式（容斥计算）：$S_2(n,m) = \frac{\sum_{k=0}^m (-1)^k \binom mk (m-k)^n}{m!}$。求单个一般用这个，然而这个东西本质上是个卷积，因此也可以 $\mathcal O(n \log n)$ 求出 $S_2(n,0\dots n)$。
• 常幂 $\to$ 下降幂：$x^{n}=\sum_{i=0}^{n} S_2(n,i) x^{\underline{i}}$。

$\text{Bell}$ 数

• 意义：$B_n$ 表示将 $n$ 个元素划分成若干个非空集合的方案数。
• 递推公式：$B_{n} = \sum_{i=0}^{n-1} \binom {n-1}{i} B_i$。
• $B_n = \sum_{i=0}^n S_2(n,i)$。

分拆数

• 意义：将 $n$ 进行整数分拆的方案数。
• 递推公式：$F_{n} = \sum_{k \ge 1} -(-1)^k (F_{n-\frac{k(3k-1)}{2}} + F_{n-\frac{k(3k+1)}{2}})$，边界为 $F_0 = 1$。
• 按照递推公式求分拆数是 $\mathcal O(n \sqrt n)$ 的，其中 $\frac{k(3 k \pm 1)}2$ 是五边形数。
• 分拆数还蛮小的，因此数据范围如果是两位数可以考虑一下 DFS 划分方案。

$\text{Bernoulli}$ 数

• $\mathcal O(k^2) - \mathcal O(k)$ 求 $k$ 次幂和。
• 设等幂和 $S_m(n) = \sum_{k=1}^n k^m$，有公式：$S_m(n) = \frac{\sum_{k=0}^m \binom {m+1}{k} B^+_k n^{m+1-k}}{m+1}$。
• 其中 $B^+_k$ 为 $\text{Bernoulli}$ 数，$B^+_n$ 与 $B^-_n$ 为两种不同的定义，仅在 $n=1$ 时有区别：$B^+_1 = \frac 12$，$B^-_1 = -\frac 12$。
• 递推公式：$\sum_{k=0}^m \binom {m+1}{k} B^-_k = 0$，边界为 $B^-_0 = 1$。
• 如果公式忘记了，还可以拉格朗日插值，$k$ 次幂和构成 $k+1$ 次多项式。

容斥

• 在组合计数问题中出现「恰好」考虑容斥。
• 多重集的组合数考虑容斥。
• 容斥本身是指数级的，因此很可能还要把容斥系数放到 DP 中去计算方案数。
• 数量大于一半的数只有一个。
• 二项式反演：若 $f(n) = \sum_{k=0}^n \binom nk g(k)$，则 $g(n) = \sum_{k=0}^n (-1)^{n-k} \binom nk f(k)$；若 $f(i) = \sum_{j = i}^n \binom ji g(j)$，则 $g(i) = \sum_{j=i}^n(-1)^{j-i}\binom{j}{i}f(j)$。
• Min-Max 容斥：对于一个集合 $S$，有 $\max(S) = \sum_{T \subseteq S}(-1)^{|T|+1} \min(T)$，$\min(S) = \sum_{T \subseteq S}(-1)^{|T|+1} \max(T)$，这两个式子在期望下也成立。常用于 $i$ 出现的概率为 $\frac{a_i}{\sum a}$，问第一次出现某个状态的期望时间，此时的答案就是 $\max(S)$，转成 $\min(T)$ 求。
• kth Min-Max 容斥：$kth\max(S) = \sum_{T \subseteq S}(-1)^{|T|+k} \binom {|T|-1}{k-1} \min(T)$，$kth\min(S) = \sum_{T \subseteq S}(-1)^{|T|+k} \binom {|T|-1}{k-1} \max(T)$，这两个式子在期望下也成立。

生成函数

• $\sum_{n\ge 0} x^n = \frac{1}{1-x}$。
• 若一个集合 $A$ 是由若干个集合 $B$ 组合而成的，那么 $A(x) = e^{B(x)}$，其中 $A(x),B(x)$ 分别为 $A,B$ 的 EGF。

Prufer 序列

• $n$ 个点的树和长度为 $n-2$ 值域 $[1,n]$ 的序列一一对应。
• 对树构造 Prufer 序列方式为：每次选择一个编号最小的叶节点并删掉它，然后在序列中记录下它连接到的那个节点，重复 $n-2$ 次。
• 每个点在序列中出现的次数是其度数 $-1$，因此限定若干个点的度数求树的方案数可以直接对 Prufer 序列计数。
• $k$ 个连通块的图，加 $k-1$ 条边使图连通的方案数为 $n^{k-2}\prod_{i=1}^k s_i$。
• 枚举 $n$ 个点的树，先枚举 Prufer 序列，然后还原成树。

矩阵树定理

• 无向图生成树：$D-A$ 的行列式。
• 求行列式如果模非质数，需要辗转相除，但要注意交换两行行列式取反。
• 无向图生成树边权和：将每条边的贡献写成一个一次函数 $wx+1$，其中 $w$ 为边权，则无向图生成树边权和就是行列式中的一次项系数，做模 $x^2$ 意义下的高斯消元即可。
• 有向图生成树：
  • 根向树形图：枚举根 $k$，$D^{out} - A$ 去掉第 $k$ 行和第 $k$ 列求行列式。
  • 叶向树形图：枚举根 $k$，$D^{in} - A$ 去掉第 $k$ 行和第 $k$ 列求行列式。

群论

• 在置换群中，等价类个数为所有置换 $f$ 的 $k^{m(f)}$ 的平均数，其中 $k$ 为颜色数，$m(f)$ 为 $f$ 的循环节。

博弈论

Nim 博弈

• $n$ 堆石子每堆 $a_i$ 个，每次可以取一堆中的若干个，先手必胜当且仅当 $\mathrm{xor}_{i=1}^n a_i \ne 0$。
• 扩展一下，每次可以取 $k$ 堆中的若干个，则对于每个二进制位统计 $a_i$ 中有多少个数在这一位上为 $1$，若每一位的个数 $\bmod(k+1)$ 都为 $0$，则先手必败，否则先手必胜。
• 阶梯 Nim：每次可以取一堆中的若干个放到前一堆中，最终所有石子都在第 $0$ 堆，则先手必胜当且仅当 $\operatorname{xor}_{i=1}^n [i \bmod 2 = 1] a_i \ne 0$。

SG 函数

• DAG 上每个点的 $\mathrm{SG}$ 值为所有后继节点的 $\mathrm{mex}$，一个状态必胜当且仅当 $\mathrm{SG} \ne 0$。
• 多个 DAG 就是用 SG 函数做 Nim 博弈。
• SG 函数的上界为 $\mathcal O(\sqrt n)$。

数据结构

并查集

• 拆点处理无向关系。
• Kruskal 重构树很有用，跟笛卡尔树很相似。
• 并查集可以带权，不过用得比较少。

树状数组

• 树状数组上二分，左儿子 p - ((p & -p) >> 1) 右儿子 p + ((p & -p) >> 1)，不要写成递归的了。
• 二维树状数组跟一维写起来没啥区别，用于维护二维前缀和，单次操作 $\mathcal O(\log^2 n)$，空间复杂度 $\mathcal O(n^2)$。

线段树

• 线段树是可以维护矩阵的，经典应用就是动态 DP。
• 楼房重建式的线段树复杂度 $\mathcal O(n \log^2 n)$，常数很小。
• 区间最值操作，即区间取 $\min$ 或取 $\max$，以取 $\min$ 为例，线段树维护最大值及个数与次大值，然后该剪枝的剪枝复杂度就对了。
• 区间/前缀/后缀都可以拆成 $\mathcal O(\log n)$ 个不交的区间再处理，前/后缀的时候可以考虑树状数组减小常数，区间就只能线段树了。应用包括优化建图，有限制的转移。
• 关于多次操作后线段树上 lazy tag 的组合计数问题，将每个节点分成三个状态：自己和祖先都无标记，自己有标记，自己无标记祖先有标记。然后直接 DP，甚至可以矩阵加速。

树链剖分

• 树剖求 LCA 比倍增常数小很多。

分块

• 当涉及到 $\mathcal O(1)$ 修改 $\mathcal O(n)$ 查询，或者 $\mathcal O(n)$ 修改 $\mathcal O(1)$ 查询的问题时，想想能不能分块做到 $\mathcal O(\sqrt n)$。

莫队

• 不太好维护的时候想想莫队，即使拿不到满分也能多拿一点。
• 注意块大小应该取 $\mathcal O(\frac{n}{\sqrt m})$，此时的复杂度为 $\mathcal O(n \sqrt m)$。
• 设 $n,m$ 同阶，如果修改和查询的复杂度都是 $\mathcal O(\log n)$ 的，但修改次数为 $\mathcal O(n \sqrt n)$，查询次数为 $\mathcal O(n)$，此时复杂度为 $\mathcal O(n \sqrt n \log n)$。考虑将修改复杂度变成 $\mathcal O(1)$，查询复杂度变成 $\mathcal O(\sqrt n)$，那么复杂度优化为 $\mathcal O(n \sqrt n)$。这种平衡的思想很重要，在很多地方都有用。
• 奇偶性优化效果还蛮明显的，即对于 $\lfloor \frac lT \rfloor$ 为奇数的块，$r$ 从小到大排序；对于 $\lfloor \frac lT \rfloor$ 为偶数的块，$r$ 从大到小排序。
• 带修也可以搞莫队，复杂度 $\mathcal O(n^\frac 53)$。
• 当删除不太容易时，考虑回滚莫队，即对于左端点在同一块的询问一起处理，每次处理询问时，钦定初始的左端点为当前块下一块的开头，然后先移动右端点，记录下答案后再移动左端点，询问完后还原记录下的答案。
• 树上莫队就是在欧拉序上跑莫队，区别在于：
  • 只考虑区间内出现了一次的点。
  • $\textrm{LCA}$ 需要单独考虑。

点分治

• 点分治其实就是树上的二分，因此如果部分分有链上二分，那放到树上就考虑一下点分治。

01Trie

• 碰到异或就三种方法：利用每位独立的性质搞事情、01Trie 上搞搞、线性基。
• 如果既有异或又有 $+1$ 操作，那就倒序往 01Trie 上插，$+1$ 操作就相当于对一条从根开始的链上所有的节点交换左右儿子。

平衡树

• 平衡树本来就不太熟练，如果考到了可以用 01Trie 代替。
• set 可以维护不交的区间赋值信息，应用中 ODT 在随机数据下效果很好。

LCT

• $\mathrm{access}$ 操作本身就可以出成题目。
• LCT 维护子树信息：只需要多维护虚子树的信息总和即可，实现中只有 $\textrm{access}⁡(p)$ 和 $\textrm{link}⁡(p)$ 需要进行小小的修改。

CDQ 分治

• 求一个序列，序列的前面会影响后面，但影响是独立的（也就是说 $i \to j$ 的影响只和 $i$ 的值有关），这种情况下可以用一个 $\log$ 的代价 CDQ 分治。

整体二分

• 多次二分且结构类似，就可以一起二分，代价同样也是一个 $\log$。

线段树分治

• 当操作只在一段时间内有效的时候，用线段树将这段时间分成 $\mathcal O(\log n)$ 段。
• 遍历整颗线段树，到达每个节点时执行相应的操作，然后继续向下递归，到达叶子节点时统计贡献，回溯时回退即可。

可持久化

• 可持久化维护的都是值域，可以方便的提炼出一段区间对应的数据结构。

可回退化

• 可回退化一般就直接拿个栈记录修改操作，回退时反向执行即可。

树套树

• 其实就是将一个值拆成 $\mathcal O(\log n)$ 个放到线段树上的每一层，一般适用于拆成多个不影响维护的信息的时候。

线段树合并

• 只用保证每次删掉一个节点就能保证复杂度，不需要启发式合并。

启发式合并

• 数据结构的合并别忘了启发式合并，那样直接保证了复杂度（因此可并堆屁用没有）。
• 会有把数据结构当成状态的树形 DP，此时的转移就是启发式合并。

dsu on Tree

• 对于每个节点，最后一个计算重儿子，然后直接继承重儿子的信息，再重新计算一次轻儿子的信息，复杂度 $\mathcal O(n \log n)$。

长链剖分

• 可以用来优化树上以深度为下标的 DP。
• 类似 dsu on Tree 直接继承重儿子的信息，不同的是对于每个节点先计算重儿子的信息，直接继承后再算轻儿子，复杂度 $\mathcal O(n)$。
• 直接继承可能需要指针维护。

笛卡尔树

• 建树直接 $\mathcal O(n \log n)$ ST 表，写什么单调栈。
• 也可以自底向上隐式建树，那就是排序然后并查集（启发式）合并，这个好像更好写，DP 也可以在合并的时候直接做。

虚树

• 询问中某个量之和为 $n$ 时：
  • 如果是在树上，考虑虚树。
  • 这个量只有 $\mathcal O(\sqrt n)$ 种，算过的保存下来就可以直接用。
  • 这个量 $> \sqrt n$ 的只有 $\mathcal O(\sqrt n)$ 个，可以暴力；$\le \sqrt n$ 的通常可以预处理。

k-D Tree

• 邻域查询复杂度没有保障，但是骗一骗分还是很有用的。
• 还可以随机转一个角度，再用 k-D Tree，可能就是期望复杂度了。
• 然后维护高维信息就类似高维上的线段树，如果有动态插入还要 $\mathrm{rebuild}$，系数取 $0.75$。

区间数颜色

• 先考虑最原始的区间颜色数模型，一个通常的方法就是记录前驱 $p_i$，则 $[l,r]$ 之间的颜色数为 $p_{l\dots r}$ 中 $< l$ 的数的个数，可以离线排序后用树状数组 $\mathcal O(n \log n)$ 实现。
• 若在线，可以主席树 $\mathcal O(n \log n)$ 实现。
• 若带修，可以 set + 树套树 $\mathcal O(n \log^2 n)$ 实现。
• 允许离线的情况下还可以考虑莫队，不带修时 $\mathcal O(n^{\frac 32})$，带修时 $\mathcal O(n^{\frac 53})$。

区间第 $k$ 大

• 不带修离线：整体二分。
• 不带修在线：主席树。
• 带修：树套树。

连续段计数

• 如果没有重复元素，那也就是统计 $\max - \min + 1 = \operatorname{len}$ 的区间个数。
• 将右端点向右扫，用单调栈维护当前每个后缀的 $\max$ 和 $\min$，然后用线段树维护当前每个后缀的 $\max - \min - \operatorname{len}$ 的值，以及每个后缀区间的值的最小值以及最小值的个数。
• 显然 $\max - \min - \operatorname{len} \ge -1$，同时对于每个右端点 $r$，至少会有一个后缀的值为 $-1$（$l = r$ 时），因此每个右端点对答案的贡献都是当前后缀区间的值的最小值的个数。
• 时间复杂度 $\mathcal O(n \log n)$。
• 如果有重复元素，这时候我们需要统计的就是 $\max - \min + 1 = \operatorname{cnt}$ 的区间个数，其中 $\operatorname{cnt}$ 为区间中不同的数的个数，那么记录一下每个数上一次出现的位置即可。

冒泡排序与逆序对

• 冒泡排序的交换次数 $=$ 逆序对数 $\ge$ 对应位置下标差的绝对值 $\div 2$。
• 假设原本在位置 $i$ 上的逆序对数为 $c_i$，冒泡排序一轮后，位置 $i$ 上的逆序对数变为 $\max(0, c_{i+1}-1)$，相当于一个左移，减一，与 $0$ 取 $\max$ 的过程。

扫描线

• 区间和矩形操作，如果可以离线就考虑扫描线。

bitset

• 有整体位运算操作的情况下 bitset 效果还是很明显的。

Trick

• 树上统计的方法：线段树合并、启发式合并、dsu on tree、长链剖分、点分治、树上莫队。

图论

最短路

• 有个东西叫 01BFS 别忘了。

最小生成树

• 最小生成树是一种最小瓶颈生成树。
• LCT 可以动态维护 MST。

Floyd

• 传递闭包。

差分约束

• 差分约束转最长路做，似乎要 SPFA，但是它死了。

2-SAT

• 拆点处理有向关系（与并查集相对应）。
• 转 Tarjan 做。
• 构造方案就取拓扑序更大的那个，注意 Tarjan 本身就求了拓扑序，只不过是反着的。

圆方树

• 圆方树其实就是对于每一个点双建立一个方点，连接点双里的所有点，然后去掉原图的所有边。圆方树保留了图中点双的性质，同时将图简化成了一棵树。
• 如果给方点赋权为其点双对应的大小，圆点赋权 $-1$，则在原图上连接任意两点的简单路径的并集大小，就是圆方树上这两个点对应的圆点间的简单路径权值和 $+2$，其中 $+2$ 指的这两点本身。
• 圆方树一般都用来处理无向图中两点之间所有简单路径的问题。

欧拉回路

• 欧拉回路的路径方案必须在 dfs 之后放入答案，否则是错的。

二分图

• 二分图等价于图中无奇环。
• 二分图匹配在时限允许的情况下就写匈牙利算法，否则写网络流。除非要求字典序最小，那只能匈牙利。
• 二分图匹配两个要素：
  1. 点能分成两个集合，每个集合内部有 $0$ 条边。
  2. 每个点只能与 $1$ 条匹配边相连。
• 常见建图：横坐标对纵坐标，行对列，黑白相间染色。
• Hall 定理：二分图中存在完备匹配当且仅当对于 $k\in[0,n]$，任意 $k$ 个左部点都与至少 $k$ 个右部点相邻。
• 在二分图中，最小点覆盖包含的点数，等于最大匹配包含的边数。
• 二分图最小点覆盖一个要素：
  1. 每条边有两个端点，二者至少选择一个。
• 无向图的最大团，等于其补图的最大独立集。
• 二分图最大独立集大小，等于 $n -$ 最小点覆盖点数，等于 $n -$ 最大匹配边数。
• 有向无环图的最小路径点覆盖包含的路径条数，等于 $n−$ 拆点二分图的最大匹配边数。
• 有向无环图的最小可重复路径点覆盖，做一个传递闭包即转化为最小路径点覆盖。

网络流

• 最大流等于最小割。
• 点边转化、拆点、费用提前计算都是很重要的 Trick。
• 集合划分模型：
  • 有 $n$ 个物品和两个集合 $S,T$。将一个物品放入 $S$ 集合会花费 $a_i$，放入 $T$ 集合会花费 $b_i$。还有若干个形如 $u,v,w$ 限制条件，表示如果 $u$ 和 $v$ 同时不在一个集合会花费 $w$。每个物品必须且只能属于一个集合，求最小的代价。
  • 设置源点 $S$ 和汇点 $T$，第 $i$ 个点由 $S$ 连一条容量为 $b_i$ 的边、向 $T$ 连一条容量为 $a_i$ 的边。对于限制条件 $u,v,w$，我们在 $u,v$ 之间连容量为 $w$ 的双向边。
  • 当 $S$ 和 $T$ 不相连时，$S$ 能到达 $i$ 代表物品 $i$ 放入 $S$，$i$ 能到达 $T$ 代表物品 $i$ 放入 $T$。
  • 当割开 $S \to i$ 的边，意味着 $i$ 放入 $T$；当割开 $i \to T$ 的边，意味着 $i$ 放入 $S$；当割开 $u,v$ 之间的边，意味着 $u,v$ 不放入同一个集合。
  • 因此最小割就是最小花费。
• 平面图最小割等于对偶图最短路。
• 上下界网络流：
  • 无源汇上下界可行流：
    1. 如果把 $r-l$ 作为容量上界，$0$ 作为容量下界，就是一般的网络流模型。
    2. 然而求出的实际流量为 $f_i + l_i$，不一定满足流量守恒，需要调整。
    3. 设 $d_{u}^{in} = \sum_{y_i = u} l_i$，$d_{u}^{out} = \sum_{x_i = u} l_i$，$d_u=d_{u}^{in}-d_{u}^{out}$。
    4. 新建源汇 $S,T$，$S$ 向 $d>0$ 的点连边，$d<0$ 的点向 $T$ 连边，容量为相应的 $d$。设 $s$ 为 $S$ 向外连边的流量和，显然 $s$ 也是向 $T$ 连边的流量和。
    5. 在该网络上求最大流，若最大流为 $s$，则每条边的流量 $+$ 下界就是原网络的一个可行流，否则无解。
    6. 具体实现时，可省略 $d_{u}^{in},d_{u}^{out}$ 数组，直接在 $d$ 数组上修改。
  • 有源汇上下界可行流：从 $T$ 到 $S$ 连一条下界为 $0$，上界为 $+\infty$ 的边，把汇流入的流量转移给源流出的流量，转化为无源汇的网络，然后求解无源汇上下界可行流。
  • 有源汇上下界最大/小流：二分答案，转化为可行流。
  • 费用流是类似的。
• 最大权闭合子图：
  • 建立源点 $S$ 和汇点 $T$ ，源点 $S$ 连所有点权为正的点，容量为该点点权；其余点连汇点 $T$，容量为该点点权的相反数，对于原图中的边 $(x,y)$，连边 $(x,y,+\infty)$。建图跟上下界网络流有点相似。
  • 最大权闭合图的点权和等于所有正权点权值和减去最小割，上述图的最小割包含 $S$ 到不在最大权闭合图内的正权节点的边和在最大权闭合图内的负权节点到 $T$ 的边。
  • 在残量网络中由源点 $S$ 能够访问到的点，就构成一个点数最少的最大权闭合子图。

最小斯坦纳树

• 对于一张无向图，求包含若干个关键点的最小生成树。
• 状压，设 $f_{i,S}$ 表示以 $i$ 为根包含了关键点集合 $S$ 的最小生成树权值，转移类似最短路，复杂度 $\mathcal O(n\cdot 3^k+m\log m\cdot 2^k)$。

三元环

• 找无向图三元环复杂度 $\mathcal O(m \sqrt m)$，方法：

  1. 先求出每个点的度数。

  2. 给边定向，对于一条边，度数大的向度数小的定向，度数一样则编号大的向编号小的定向，形成一个 DAG。

  3. 计数时枚举 $x$，对出边到达的点打 $y$ 标记，对于所有出边到达的点再枚举出边到达的点 $z$，如果 $z$ 上有 $y$ 标记，则 $x,y,z$ 为一个三元环。

计算几何

向量

• 点积（做功大小）：$p_1 * p_2 = x_1x_2 + y_1y_2 = p_2 * p_1$。
• 叉积（有向面积）：$p_1 \times p_2 = x_1y_2 - x_2y_1 = -p_2 \times p_1$。
• 旋转：$X = x \cos(a) - y \sin(a)$，$Y = x \sin(a) + y \cos(a)$。

直线

• 直线交点：解方程。
• 点到直线的距离：叉积除以底。

平面图

• 欧拉定理：点数 $+$ 面数 = 边数 $+2$，实在忘了随便画一个平面图。

多边形面积

• 三角剖分。

二维凸包

• 排序后单调栈。

旋转卡壳

• 求平面最远点对。
• 其实还是利用凸包的单调性。

半平面交

• 极角排序后单调队列。

曼哈顿距离和切比雪夫距离

• 曼哈顿距离：差的绝对值相加。
• 切比雪夫距离：差的绝对值取 $\max$。
• 曼哈顿距离 $\to$ 切比雪夫距离：$(x, y) \to (x + y, x - y)$。
• 切比雪夫距离 $\to$ 曼哈顿距离：$(x, y) \to (\frac{x+y}{2},\frac{x-y}{2})$。

闵可夫斯基和

• 对于两个凸包 $A,B$，从原点向 $A$ 中的每个点做一个向量，将 $B$ 中每个点沿所有向量移动得到的所有位置的并就是闵可夫斯基和，具有交换律。
• 闵可夫斯基和就是将两个凸包的边极角排序后顺次连接起来即可，可以直接归并排序。

交互题

• 先想二分。
• 一定要考虑随机化，有的算法看起来不能过随机化可能就能过了。
• 如果出现树，想想能不能剥叶子。

提答题

• 提答题分两类。
• 一类是十个点基本没啥关系，比如造计算机题，这种题的得分一般跟花费时间成正比。
  方法是先全部看一遍，拿一些很容易的分，然后再根据剩余时间权衡一下，碰到一看就不是很好拿分的点就扔了。
• 另一类是给一个 NPC 问题（或者复杂度很高的问题），每个测试数据都有特殊的性质，可能还会根据答案的优劣程度给分。
  方法是先写通解和乱搞，再去一个点一个点的看，同样要根据剩余时间权衡。

调整法

• dmy 教的一个似乎比较优的乱搞方法。
• 每次都在严格不变劣的前提下随机调整，如果调整更优则直接调整，否则随机判断是否调整。
• 适用条件：要能一直调整下去，这样很难陷入局部最优解。
• 一般图最大匹配：随机一个没匹配的点，如果有和它相邻的点没匹配，就匹配，否则随机匹配和它相邻的一个点，断掉那个点原本的匹配。
• 一般图最大独立集：随机一个可以直接加入独立集的点加入，如果没有，随机一个加入后只会将一个点删除的点，随机判断是否加入。
• 调整东西一般都很直接，不需要经过什么转化。

Trick

• 有的时候可以直接借助 checker 跑乱搞。
• 不要写模拟退火，效果差，我也不熟。