跳跃
- 带修可以考虑 \(\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
