数据结构

还是决定单独拎出来写...

线段树

好像自己从来没写过动态开点（？）

动态开点

顾名思义，动态的开线段树上的节点，以达到节省空间的目的，这种技巧我们常用在普通线段树无法开下/值域过大时可以使用，动态开点线段树上的区间修改需要用到标记永久化，当然标记需要满足结合律和交换律，互相覆盖的标记是用不了的。

给一个单点加，区间查询的代码，树状数组1。

code

标记永久化

直接接着上文讲了，会发现，在动态开点线段树上，我们不太好维护区间加法，每次下传标记空间还是会爆掉，我们此时考虑每个点的标记不进行下传，查询时把路径上的标记再统计上即可，当然，这种思路只能适用于一些满足结合律和交换律的东西上，比如加法）。而且，这玩意不仅可以用在动态开点线段树，主席树，或者一些难以下传标记的东西里面。

例题：SP11470，CF960H，P3313。

一个是主席树区间加的板子，一个是标记永久化+树剖+期望，一个是树剖+动态开点线段树，从另一篇博客抄过来的啦，会补的，别急。

维护历史信息

吉老师线段树，还要维护多个信息。

线段树二分

线段每个区间上二分以处理某些问题。

李超线段树

线段树每个节点维护最优线段，以中点作为比较的依据，假设现在有两条线段 \(l_1\)，\(l_2\)，假如 \(l_1\) 在这个区间的中点高于 \(l_2\)，那么显然他在这个区间更优，交换最优线段（默认取最大 \(y\) 值）,显然这样并没有结束，继续向左右分治，重复上述过程，就能够维护这条线段，而我们需要在线段树上将这条线段拆成 \(\log\) 条，然后分别向下传递，所以插入复杂度 \(\log^2\)，查询时我们考虑便利到每一个区间看看当前区间的最优线段在 \(k\) 的取值，然后取个最大值即可，挺好理解的。

依次，我们就可以维护平面内多条线段，发现斜率优化也是用这东西，所以很多斜率优化的题就可以李超树，会在 dp 专题写的。

动态开点code

可持久化

写完动态开点就感觉这东西很简单了，考虑我们要维护每个时间戳下的线段树，暴力建出所有线段树显然是空间爆炸的，我们可以利用动态开点，记录每棵线段树的根，分别作操作，单点修改就普通的直接修改，区间修改就需要标记永久化了，具体地，我们不进行下传标记的操作，因为这样我们的空间还是会爆炸，我们把只修改每个拆分出的小区间的标记，进而在查询时依次合并信息做到保证时间和空间复杂度。区间加板子 SP11470。

感觉现在是懂了主席树的思想了，考虑我们有一个静态区间问题，比如 P1972 [SDOI2009] HH的项链，我们要询问静态区间不同颜色数，其实可以用类似动态扫描线的做法，扔到主席树上，每个主席树维护前缀区间的信息，然后差分出答案，比方说这题我们是令答案为 \(\sum_{i=l}^{r} [las_i < l]\)，然后在两棵前缀主席树上作差查询答案，其实这里的主席树就可以看做动态开点的权值线段树了。

再者就是查询区间第 \(k\) 大的问题，也是两棵权值线段树作差，然后比较左右子树的大小再向左/右，跟平衡树查询的思路是一致的。给一个裸题 P2633 Count on a tree，树剖+主席树维护 \(k\) 小值，具体来讲，我们需要维护从每个点到根的前缀主席树，然后答案就是 \(rt_u+rt_v-rt_{lca}-rt_{fa_{lca}}\)，所以我们需要维护四棵主席树作差的查询 (。

练习

P2824

二分不好想到，但想到二分就秒了，首先考虑 01 序列怎么搞，排序就简单的查个数量然后直接覆盖，但是考虑怎么将原序列变成 01 序列，发现我们可以固定一个阀值，大于就 1，小于就 0，交换完成之后再查询选点的值，显然，选点最后一个为 1 的值就是答案，所以这东西是具有单调性的，可以二分，复杂度 \(O(n\log^2n)\)。

P3313

总算是填了前面的大坑，动态开点+树剖，板子题，就是注意细节，树剖都能写错我也是唐完了。