wqs 二分

应用场景：恰好选 $k$ 个，凹凸性。

一维 dp 中的斜率优化与四边形不等式

斜率优化：

回滚莫队速成

正常的莫队中，我们使用 $L,R$ 两个指针的移动来框出区间 $[l,r]$，可以发现这种移动是不满足可撤销性的。
如果我们换一种指针的移动方式，使莫队具有可撤销性，那么配合可撤销数据结构就可以维护更多东西了。

整体二分的不带修写法

对于每个询问都可以二分的题目，可以将所有询问放在 vector 中。假设当前二分的答案区间为 $[l,r]$，按照比较结果把询问分成答案在左边和答案在右边，递归处理答案在左边 $[l,mid]$ 和答案在右边 $[mid+1,r]$。
但是每次都进行 check 时，需要把 $[l,r]$ 这一段的所有操作拿出来，太慢了。不妨使用类似莫队的方法，使用一个指针来辅助快速 check。

最小生成树边权期望

在一张 $n$ 个点的完全图中，每条边的权值是 $1\sim m$ 中的一个整数，求最小生成树权值的期望。

魔法序列 题解

给定一个序列 $a$，$q$ 次询问，每次询问给定一段区间 $[l,r]$ 和一个数 $x$，求

数位 dp

数位 dp 的题往往具有以下特征：

• 要求统计满足一定条件的数的数量
• 判定条件和数位上的值有关
• 询问是一个区间 $l\sim r$，有时也只有上界
• 区间很大，往往超过 $10^9$，暴力会超时

FWT 的矩阵理解

在学习 FFT 的时候，我们对序列 $A,B$ 做了一次 $\mathrm{dft}$ 变换，将函数值转化为了点值，使得 $\mathrm{dft}A_i\times\mathrm{dft}B_i=\mathrm{dft}C_i$，这样我们再对点值 $\mathrm{dft}C_i$ 做一次 $\mathrm{dft^{-1}}$ 变换，就将点值还原成了序列。

FHQ_Treap

废话少说，普通平衡树用 pbds 写写就好了，没必要学，不如直接来学 FHQ_Treap。

CF662C Binary Table 题解

将列的状态作为 bitmask $i$，记 $a_i$ 表示状态为 $i$ 的列的出现次数，$\operatorname{pop}(i)=\min(\operatorname{popcount}(i),n-\operatorname{popcount}(i))$。