分治树 · Zhl2010 第二博客

操作序列

操作序列处理方式：操作树，操作序列，操作序列分块，操作序列 CDQ 分治，操作序列分治树，二进制分治树，操作序列划分树二分。

维护各操作在操作序列生效区间，用操作序列分治树，常见的可以配上并查集等算法使用。

P4588 [TJOI2018] 数学计算。这道题需要维护的看似是乘法，然后可能撤回之前的某一次，实际上我们需要用可撤销，或者是可修改数据结构，然后撤销就是将那一个改成 $1$ ，问题就能用线段树做了。

关键点，首先是要观察到题目需要让你能够撤销操作，转化成修改，然后修改就是相当与分治树中的一连串的变化，上传。

这道题是 01trie + 线段树。

首先是已经有的数，只需要用 trie 可以直接解决。

然后这道题有两个维度，时间和下标， trie 可以处理时间，线段树就处理下标。

trie 相当于是与权值挂钩，记录当前权值中时间最大的，询问需要保证时间符合要求。

所以这道题的关键点就是找准需要维护的维度，然后寻找对应数据结构。

比较有用的一个常见思路。

一个左右端点问题我们可以用分治。

分治中左区间对右区间中的点做贡献，这样算不会重复，跟 cdq 有点类似。

CDQ 生效区间为偏序，修改支持差分。

分治树有后效性，不支持差分。

操作分块经常用于信息不可合并的情况。

定期重构。

首先列出转移方程，我们算上下标总共有三个要求，而且都是要求前面的才能给后面的转移。

这种可以直接用 cdq 分治优化了，然后注意的是需要左边先，然后算左边对右边的贡献，然后再算右边的。

这道题需要算概率，只需要算出有多少种方案经过了这个点，然后除以总方案数就行了。

算经过这个点的概率需要计算从前往后保证最大的方案数和从后往前的，计算时需要保证他们的长度拼起来是最大的。

我还因为关了同步，然后 cout 和 printf 混用，调了好久。

这是一个动态的算法，看这道题：

这道题的主要思路是先列出 dp 式子，然后用线段树做。

线段树每一个节点记录前面对他的影响和他对后面的影响，然后可以做到快速更新。

主要就是需要算出这一段如果前面是谁，会有什么样的答案，然后最后是谁的时候答案是多少。

然后 dp 状态就是 $f_{i,j}$ 表示在编号为 $i$ 的线段树区间，此时匹配到了 $j$ 。