几种离线分治算法
现在只有口胡. 别急.
这些算法口胡起来很舒服啊. 但是沾点离线的一般都不太好写/ng
转一手 cmd 的 blog
Stop learning useless algorithms. Go and solve some problems, using binary search.
1. cdq 分治
大致思路是, 强制让修改在查询之前.
我们直接把一个操作序列分成两半, 一次算完前面的修改对后面查询的贡献, 然后分治下去.
这个操作要求可以先算一些修改的贡献, 再算另一些修改的贡献.
2. 整体二分
每个询问二分一遍太慢了.
所以我们考虑直接一起二分掉, 换句话说我们共用了判定的 mid.
每次判定完之后, 按照结果将询问划分到两边, 继续二分下去.
3. 线段树分治
最先学会的一个 (?
用处在于, 把删除操作转成撤销操作, 而后者是容易的.
方法是, 我们处理出来每个元素存在的时间段 (从插入到删除).
然后对着时间开线段树, 这样贡献就变成了线段的形式, 直接扔到线段树上拆成 \(O(\log n)\) 段.
然后对着线段树 dfs 一遍就完事了, 此时只有加入和撤销.
4. 猫树分治
喵喵喵.
猫树的精神在于预处理从中间往两边的贡献, 然后直接合起来.
所以这个东西也可以拿来分治, 每次处理经过中点的所有区间, 剩下的下放到两边.