跳跃

• 带修可以考虑 \(\sqrt{n}\) 分块维护
• 若是跳次数超多可以考虑倍增维护
• 很多有循环/置换环的东西可以把一次转换看成“跳跃”

dp抽象

• 网格图抽象：把状态看做网格图上的点，观察性质

• 分层 dp 抽象：把每层画出，把转移边画出，看是否能通过平移等做内联 dp

子集枚举

for(S=(1<<n)-1; S; S--)
	for(k=S; k; k=S&(k-1));

\(O(3^n)\)

LIS 最长上升子序列

• 分层技巧：对每个 \(i\) 以 \(f_i\) (以 \(i\) 结尾的 LIS 长度) 分层，可以用来做很多东西。P7931
  • 注意到一个性质，每层里面的点是 \(i\) 递增，\(a_i\) （值）递减的，即下降的
  • 考虑构造序列的话有一个贪心：每次 \(k\) 向 \(k+1\) 层选的时候，一定先选 \(k+1\) 层中 \(i\) （下标）最前的，相当于对下次 \(k\) 层向 \(k+1\) 层中选数时，可以选到一个更小的数（而且如果上一次不选最前的，当前这次有可能选不到，因为交错了）

LCT 连通性

LCT维护过动态图联通性 \(\rightarrow\) 如果可以离线的话，我们可以在LCT上维护关于删除时间的最大生成树。当新加入一条边后，树上肯定成环，则只需要删掉环上删除时间最早的那条边即可。

可达性

魔塔

询问一个东西可否可以实现，考虑其可达性，比如夹在 \([l, r]\) 之间就可达，这样只用维护 \(l,r\)

可用于 \(\pm 1\) 折线图，只要存在 \(l, r\) 那么 \(x\in[l,r]\) 都存在

在连续的区间中，最大最小值以下都可达，问是否能有一个排列判定最大值即可CF1895D

区间操作

• 魔塔
• 对 \(01\) 串 \(flip\) （每位取反）相当于将每个位置前缀和 \(\times (-1)\)
• 区间 \(reverse\) 相当于交换维护的前后缀信息，一般要用排名平衡树维护

hash

• 多用于匹配，可以解决树上问题，序列问题
• 具有可加可减性，树上路径hash值有的可以直接树上前缀减 系统设计
• 据说自然溢出 \(hash\) 的碰撞概率为 \(\frac{1}{\sqrt p}\) ，所以可以使用 \(ull\) 据说 \(base\) 要用 \(131\),\(13331\),\(131313131\) 等质数

随记

• \([s / x] * x = s - s\) \(mod\) \(x > s / 2\)

• 求总边权，拆贡献，对每条边分别算出现的贡献

串并联图/图的收缩

很多问题是稀疏图，（dp）值可以直接在边上传递，此时看看出入度为 1 的点是否能缩起来 abc372f