思路

线段树合并叶子的贡献也包括 $pre$ 和 $suf$。
数组尽量要定义到一起，不然急了之后可能就忘了修改。
有关 $\operatorname{mex}$ 的题目，线段树维护 $Seg_r$ 表示 $r$ 为右端点时满足条件最大的左端点 $l$ 使之 $\operatorname{mex}(l,r)=x$，当 $x\rightarrow x+1$ 时，$Seg_r$ 整体不增，且 $Seg$ 从 $1\sim n$ 单调不降。
求多起点网格单位权最短路，将所有起点扔进队列 bfs() 即可。
*当需求出近似答案区间在 $[0.5ans,2ans]$ 时，二进制倍增可能方便的得到 $[0.5ans,1ans]$ 的答案。
*对于维护楼梯数字（每一位数字都大于前一位数字的数），考虑用 $1111\cdots111,111\cdots111,\cdots,111,11,1$ 相加得到，采用分阶段 dp 维护相关性质。
当树上从祖先走一条固定路径到后代，但路径不好直接维护时，考虑转换为后代 $\rightarrow$ 祖先，再去判断路径是否匹配。
维护集合是否相同采用设定 $key$ 值 $\texttt{Hash}$ 维护。
考虑字符串变换时如果操作有互逆性，将字符串操作为字典序最小的字符串，然后比较 $x$ 和 $y$ 操作的最小字典序字符串 $x’$ 和 $y’$ 是否相同。
对于关于斜率为 $k$ 的直线，每个坐标转化为 $(x_i-x_i\cdot k,y_i)$ 变成比较斜率为 $0$ 的直线。
如果某一题目中动态规划的状态可以**分成两个独立的条件 $X$ 和 $Y$**，将其分成 $f_X$ 和 $g_Y$ 分别计算，最后将其合并。
不要忘记线段树维护矩阵乘法。
关于树上直径的期望，考虑枚举直径的最长长度，然后在这个长度下做 dp，设 $f_{u,j}$ 表示子树 $u$ 内最长直径为 $j$ 的概率，枚举 $f_{u, j}+f_{v,k}\rightarrow f’_{u,j+k+w}$。
在 DAG 上删 $k$ 个点，可以以这 $k$ 个点跑拓扑排序算贡献。
特殊最优化问题可以使用 $\texttt{Simulated Annealing}$。
做 $\texttt{Hash}$ 问题时注意随机权值值域的大小，一般情况下越大越好。
*“图上的两个点的邻域有 $k$ 个公共点时两个点也成为邻域”的计数问题，类似于 $k=1$ 连通块计数的维护方法，通过枚举连通块大小容斥进行计算。
高斯消元中，注意方程的特殊性，如系数是否为正三角/倒三角，限制是否为链式结构，往往能对复杂度进一步优化。
*形如 $f(x)=\min(x,a)+b$ 或 $f(x)=\min(\max(x,L),R)+D$ 的函数，则 $f(f(x))$ 也为同样结构。一个推导用到的恒等式：$\min(\max(x,y),z)=\max(\min(x,z),\min(y,z)),\max(\min(x,y),z)=\min(\max(x,z),\max(y,z))$。对于这样的结构，可以在线段树中的 pushup() 维护。（类似这种思想还有 ddp）
当遇到格线游走类问题有移动范围的限制时（即限制不能走到 $y=x+b$ 和 $y=x+c$ 的线上），使用反射容斥。
主席树理论上不能维护最值问题，但注意题目维护的区间如果是特殊区间（前缀/后缀），那么主席树可以维护最值。
DAG 上单点修改，后效查询是不能 polylog 的，但可以采用根号重构维护。
对于一个从 $n$ 个数选最少的数（设为 $k$ 个）使之满足某个条件时，假若 $k$ 的上界十分的小的话，考虑这样一种方法：从 $0$ 上升枚举 $k$，考虑求从 $n$ 个数选 $k$ 个数满足条件的合法方案数，如果方案数大于 $0$ 即代表此时的 $k$ 是第一个满足要求的最小值。
一个值域为 $V$ 的数的仅有最多一个大于 $\sqrt{V}$ 的质因子，对于每一个大于 $\sqrt{V}$ 的质因子 $P$，将所有数分为包含质因子 $P$ 的数和不包含，进行分阶段 dp。
出栈序：结束子树 $u$ 的 dfs 时打标记（即括号序的右括号），记作 $dfn_u$。那么再次进行中序遍历，满足点 $u$ 和一个祖先 $z$，区间 $[dfn_u,dfn_z]$ 上未被赋值的节点在中序遍历上并未访问，用于维护树上离线问题的时候不用撤销。
只关于 $i$ 和 $i+c$ 关系型计数，可以按模数分类，如按 $0,c,2c,3c,…,1,c+1,2c+1,…$ 的顺序，这样 dp 的时候状态只需要看相邻两位的关系。如果按原顺序需要连记 $c$ 个，但其实你能够发现这并不聪明，因为记录的是 $c$ 个独立结构。
在询问串的总长度较大时（不能带 log），不必把询问串都接在一起 SA（之前以为只能接在一起做），可以对于询问串，在文本串里面二分找到字典序排名最高的“字典序小于询问串的”位置，相当于在 $sa_1\sim sa_n$ 上二分，能以 $log^2n$ 的时间查询一组。

思路

实现