开个坑，记一点平时遇到的奇怪的东西（包括但不限于易错点和各种技巧）。
数据结构
-
摩尔投票求区间绝对众数：
区间绝对众数定义为区间中出现次数严格大于一半的数。考虑这样一个过程，每次删除区间两个不同元素，若存在区间众数，则最后剩下的数为区间绝对众数，可用线段树维护投票结果；用平衡树维护每种数字的出现位置，即可检验所剩数字是否为区间绝对众数。
另：不维护投票结果，在询问区间中随机找 \(k\) 次元素并判断，若存在区间绝对众数，则未找到的概率为 \(\frac{1}{2^k}\)。见 P3765。
-
懒标记是延迟对子节点信息的更新，而不是本身。
-
Splay 求前驱 / 后继的时候，若不存在前驱 / 后继，立即返回 \(0\)，其原因在于若不及时返回 \(0\)，会对 \(0\) 号节点进行
splay操作，导致根节点置为 \(0\)。 -
动态开点通过用栈存储节点的方式实现时，务必先将可用节点全部入栈。
-
Splay 更新 \(siz_x\) 的时候别忘了加上节点本身的大小 \(cnt_x\)。
-
Splay 修改序列信息时（包括序列的插入、删除和其他修改），中序遍历为序列顺序，对于修改 \([L,R]\)，将 \(L-1\) 对应的节点旋转到根，再将 \(R+1\) 对应的节点旋转到 \(L-1\) 下方，成为 \(L-1\) 的右儿子，此时 \(R+1\) 的左子树即为 \([L,R]\)。
-
由于 LCT 的虚边“认父不认子”的性质，单棵 Splay 内的根节点的父亲不一定为空，判断根节点一定要用
isroot。 -
求路径边权信息（和 / 异或和 / \(\min\) / \(\max\) 等）可转化为求点权。具体地，对于边 \((u,v,w)\)，在 \(u,v\) 间加入一个点权为 \(w\) 的点。
-
树状数组实现区间加 + 区间和：对于原序列 \(a\) 的修改 \((L,R,val)\)，等价于对差分序列 \(b\) 的单点修改 \((L,val)\) 和 \((R+1,-val)\)；对于 \(a\) 的查询 \([L,R]\)，进行差分，有：
\[\sum \limits_{i=1}^{x }a_i = \sum \limits_{i=1}^{x} \sum \limits_{j=1}^{i} b_j = \sum \limits_{i=1}^{x} (x-i+1)b_i = (x+1) \sum \limits_{i=1}^{x} b_i - \sum \limits_{i=1}^{x} ib_i \]于是我们再维护一个满足 \(c_i=ib_i\) 的序列 \(c\) 即可。
-
树状数组 \(O(n)\) 建树：由于节点 \(x\) 所管辖的区间为 \([x-\mathrm{lowbit}(x)+1,x]\)，提前维护一个原序列的前缀和即可。
-
二维树状数组：
对于单点加 + 矩阵和，开一个二维树状数组，查询和修改类似一维的情形，做一个循环嵌套，维护矩形的前缀和。类似地，对于矩阵加 + 单点值，二维差分即可。
对于矩阵加 + 矩阵和，同样仿照一维，考虑矩阵 \(a\) 的差分矩阵 \(b\)，有：
\[\begin{aligned} \sum \limits_{i=1}^{x} \sum \limits_{j=1}^{y} \sum \limits_{k=1}^{i} \sum \limits_{l=1}^{j} b_{k,l} &= \sum \limits_{i=1}^{x} \sum \limits_{j=1}^{y} (x-i+1)(y-j+1)b_{i,j} \\ &= (x+1)(y+1) \sum \limits_{i=1}^{x} \sum \limits_{j=1}^{y} b_{i,j} - (y+1) \sum \limits_{i=1}^{x} \sum \limits_{j=1}^{y} ib_{i,j} \\ & - (x+1) \sum \limits_{i=1}^{x} \sum \limits_{j=1}^{y} jb_{i,j} + \sum \limits_{i=1}^{x} \sum \limits_{j=1}^{y} ijb_{i,j} \end{aligned}\]所以用四个二维树状数组分别维护 \(b_{i,j},ib_{i,j},jb_{i,j},ijb_{i,j}\) 即可，见 P4514。
-
线段树注意修改和询问的区间是否合法，存在不合法情况要判
L>R||L<1||R>n，注意要判操作区间，而不是节点覆盖的区间。 -
分块在线区间众数
块长取 \(\sqrt n\)，离散化。我们预处理 \(f_{i,j}\)，表示第 \(i\) 个块到第 \(j\) 个块这个区间的众数的出现次数。具体来说，用一个 \(cnt\) 数组作为桶，存各数的出现次数，枚举 \(i,j\)，分别是最左侧块的编号以及要移动的右端点指针，\(j\) 从 \(l_i\) 到 \(n\) 遍历，每次对桶修改，当 \(j\) 为某个块的右端点时更新 \(f_{i,id_j}\) 的值。\(i\) 变化时，清空 \(cnt\) 数组。时间复杂度 \(O(n\sqrt n)\)。
整块直接用处理出的 \(f\) 即可，\(O(\sqrt n)\)。考虑两侧散块。为了完成这个操作，我们用一个
vector记录各元素出现的位置 \(pos\)，再用一个数组记录元素是所在的vector内的第几个元素（即它是序列中相同元素的第几个）。对于散块元素 \(a_i\)，我们考虑它是否会使当前答案 \(res\) 加上 \(1\)。若 \(a_i\) 为左侧的元素，在相应
vector内找到下标为 \(find_{a_i}+res\) 的元素 \(p\)，即从它开始向右数第 \(res+1\) 个相同元素的下标，\(p\le R\) 则 \(res \leftarrow res+1\)；若在右侧，则找 \(find_{a_i}-res\)，判断条件为 \(p\ge L\)。单次 \(O(\sqrt n)\)。注意访问不要越界。总的时间复杂度为 \(O((n+m)\sqrt n)\)，空间复杂度为 \(O(n\sqrt n)\)。
DP
-
DP 用到的数组注意预处理，包括边界值和非边界的初始化，特别注意最小化答案的题目预先置为 \(+\infty\)，预处理容易因为范围原因出错。
-
DP 转移过程中需要用覆盖的方式更新答案的，要考虑是否需要把之前求出答案存下来，例如 CF581F；此外要注意转移顺序、枚举顺序等，常见的例子是各类背包，例如 P1941。
-
由状态内情况过多引起的无法转移通常有两种解决方案，增加状态数和对状态限制。
-
计数类问题正难则反，可以用方案总数减去不合法部分。
字符串
-
不同子串个数：
子串集合与所有后缀的所有前缀构成的集合相同，后缀排序处理出 \(height\) 数组，那么字典序顺序下的第 \(i\) 个后缀造成的贡献为其长度减去 \(height[i]\)。证明：前 \(height[i]\) 个前缀一定出现过，而后面的前缀的字典序一定严格大于之前计算过的所有前缀。见 P2408。
-
在线求模式串在文本串中的出现次数：
对文本串 \(S\) 后缀排序，模式串 \(T\) 在 \(S\) 中出现当且仅当它是一些后缀的前缀，直接在 \(sa\) 数组上做两次二分，二分时比较 \(S\) 和一个后缀的字典序大小，复杂度 \(O(|T|\log|S|)\)。
-
比较子串字典序：
对于 \(S\) 的子串 \(A=S[l_1..r_1]\) 和 \(B=S[l_2..r_2]\)，若 \(\mathrm{LCP}(l_1,l_2) \ge \min(|A|,|B|)\)，则 \(A<B \Leftrightarrow |A|<|B|\)，否则 \(A<B \Leftrightarrow rk[l_1]<rk[l_2]\)。
-
多次做后缀排序需要清空 \(rk\) 数组、\(y\) 数组和 \(cnt\) 数组。
数学
-
预处理出 \(O(\sqrt n)\) 范围的质数后，对 \(n\) 分解质因数的复杂度是 \(O \left (\frac{\sqrt n}{\ln n}\right )\) 的。
-
对 \(n\) 做唯一分解后，求出各因数的积性函数值是 \(O(d(n))\) 的。
-
\(d(n)\) 的数量级大致在 \(O(n^\frac{1}{3})\)。
图论
-
竞赛图：
竞赛图定义为对于任意两点 \(u,v\) 存在且仅存在一条有向边的有向图（无向完全图对每一条边定向）。
- 性质一：竞赛图缩点后的 DAG 呈链状；
- 性质二：竞赛图一定存在哈密顿路；
- 性质三：竞赛图中的任意一个 SCC 中均存在哈密顿回路。
-
二分图：
- 最小点覆盖 \(=\) 最大匹配
- 最大独立集 \(=n-\) 最大匹配
- 最小边覆盖 \(=n-\) 最大匹配
-
注意图是否连通，是否有重边、自环。
STL
vector的insert和erase的复杂度是线性的（修改位置后方元素个数），虽然常数非常小，弱数据可以跑过平衡树，但不要尝试。
常见错误
-
数组是否开小，包括数据范围以及开两倍、四倍等，还有二分图、Splay 等要把各种数目加起来再开。
-
开
long long，甚至__int128。 -
注意取模。
-
注意 SPJ 类题目，是否要求按一定顺序输出。
-
多组数据或数组重复利用时，务必清空。
-
子函数里开的数组不会预先赋值为 \(0\)，只有全局变量会，如果使用要注意清空。