可持久化线段树

[P3919 【模板】可持久化线段树 1（可持久化数组）](https://www.luogu.com.cn/problem/P3919) 可持久化线段树裸题。 ------------ [P3834 【模板】可持久化线段树 2](https://www.luogu.com.cn/problem/P3834) 先排序去重。然后离散化，将第 $i$ 小数用 $i$ 来代替自己在权值线段树中的位置。 建立 $n$ 棵线段树，第 $i$ 棵树储存 $a_1$ 到 $a_i$ 的信息，并记录该区间数的个数。因为第 $i$ 棵线段树与第 $i-1$ 棵线段树至多只有一条链不同，也就是 $\log n$ 个节点不同，所以空间复杂度为 $O(n\log n)$。 对于 $m$ 次询问区间 $[l,r]$ 的第 $k$ 小值，及查询第 $r$ 棵线段树有，而第 $l-1$ 棵线段树没有的数的第 $k$ 小值。 若两棵树左儿子的所含的总数不大于 $k$ ，说明第 $k$ 小值在左子树，否则在右子树。 直到该区间只剩一个数，那这个数及是答案在全部数中的排名，输出即可。 ------------ [P1383 高级打字机](https://www.luogu.com.cn/problem/P1383) 对于 $n$ 个操作，若操作为 ```type```，及新建一棵线段树。叶节点保存要保存当前字符，所有节点都要保存区间的字符数。 若操作为 ```Undo```，直接将树根赋值为第 $i-k$ 个树根。 若操作为 ```Query```，直接线段树查找第 $k$ 个字符。 时间复杂度： $O(n\log n)$。 空间复杂度： $O(n\log n)$。 ------------ [P1972 [SDOI2009]HH的项链](https://www.luogu.com.cn/problem/P1972) 原本是一道莫队入门题，被加强了好几次数据，莫队水不过去了…… 设上一个与第 $i$ 个数相同的数的位置为 $last_i$，若没有则 $last_i=0$。不难发现区间 $[l,r]$ 的贝壳种类为 $\sum_{i=l}^{r} last_i<l$。 便建 $n$ 棵线段树来维护。注意，线段树维护的范围是 $[0,n]$。 查询的时候及查询两树之差中区间 $[0,l-1]$ 种类和。 ------------ [P3567 [POI2014]KUR-Couriers](https://www.luogu.com.cn/problem/P3567) 一道简单的主席树题。 建 $n$ 棵线段树，其中以 $root_i$ 为根的线段树区间 $[l,r]$ 表示前 $i$ 个数中大小在 $[l,r]$ 之间的数的个数。 查询的时候若遇到左区间或右区间的数的个数大于一半，及向该区间查询，直到区间长度为 $1$。否则返回 $0$。 ------------ [P7424 [THUPC2017] 天天爱射击](https://www.luogu.com.cn/problem/P7424) 观察问题后可以发现，可以将问题转变为第 $i$ 块木板是否会被打碎，若打碎就将打碎它的子弹的答案数加 $1$。要求第 $i$ 木板是哪个子弹打碎的，就是求打在区间 $[l,r]$ 的子弹的第 $s_i$ 小时间。 也就是求区间 $[l,r]$ 的第 $s_i$ 小值，这就转变为我们所熟悉的静态求区间第 $k$ 小值。 注意可能有多个子弹打在同一个位置上，这个时候需要按顺序加入主席树。还有就是要判断该区间的子弹数是否超过 $s_i$，否则根本就没有第 $s_i$ 小值。 ------------ [P2633 Count on a tree](https://www.luogu.com.cn/problem/P2633) 本题的意思就是求树上两点间的第 $k$ 小值。其实很简单。 对于每个节点都建立一个线段树，维护的区间是根节点到当前节点。 设 $w=lca(u,v)$，不难发现树上 $u$，$v$ 间的数的个数 $cnt$ 为 $$s[u].cnt+s[v].cnt-s[w].cnt-s[fa[w]].cnt$$ 若 $cnt\le k$，说明第 $k$ 小值在左区间。否则就在右区间。 ------------ [P4587 [FJOI2016]神秘数](https://www.luogu.com.cn/problem/P4587) 一道挺有意思的题。对于查询区间 $[l,r]$，假设已经放进了一些数，可以组成 $[1,pos]$ 中任何一个数。要新加入一个数 $x$。 观察后可以发现，若 $x\le pos+1$，就把 $x$ 加入，那就可以组成 $[1,pos+x]$ 中任何一个数。否则 $x>pos+1$，就算把 $x$ 加入，也无法组成 $pos+1$，故不将 $x$ 加入。 我们先将区间 $[l,r]$ 的数排序，从小到大。（实际上并不需要） 最开始可以组成的区间为 $[0,0]$。 设 $maxn$ 为加入集合的上界（不一定有这个数，但是集合内的数都小于等于它），初始为 $0$。设 $pos$ 为当前可以表示 $[1,pos]$。 最开始，肯定要放入数字 $1$。若没有数字 $1$，那肯定组不成 $1$，就可以直接输出。假设数字 $1$ 的个数为 $cnt$，那组成的范围就成了 $[1,cnt]$。此时 $maxn=1,pos=cnt$。 按照之前发现的一些性质，继续查找数。 首先，新加入数肯定要在 $[1,pos+1]$ 内，又因为小于等于 $maxn$ 的数已经被加入，所以新加入的数范围在 $[maxn+1,pos+1]$。查询区间 $[l,r]$ 中范围在 $[maxn+1,pos+1]$ 内的数的和 $res$。 将这些数全部加入，可组成的范围变为 $[1,pos+res]$，$maxn$ 变为 $pos+1$。这样操作，直到加入不了数。答案就是 $pos+1$。 原本说要先排序，实际是不需要的，只需返回区间 $[l,r]$ 范围在 $[maxn+1,pos+1]$ 数的和，这就可以用主席树来维护。 ------------ [P3605 [USACO17JAN]Promotion Counting P](https://www.luogu.com.cn/problem/P3605) 主席树裸题。先树剖，然后建立权值线段树，然后求区间内有几个大于 $p_i$ 的数就好了。 ------------ [P3293 [SCOI2016]美味](https://www.luogu.com.cn/problem/P3293) 按位贪心。然后用主席树维护区间内一个值域内的数的个数即可。 ------------ [P3963 [TJOI2013] 奖学金](https://www.luogu.com.cn/problem/P3963) 先按分数排序。 然后枚举学生成绩的中位数，找 $\dfrac{m}{2}$ 个小于他成绩的人，并使得奖学金最少。 再找 $\dfrac{m}{2}$ 个大于他成绩的人，并使得奖学金最少 。 最后再加上这个人要的奖学金。 具体，建 $n$ 棵权值线段树，第 $i$ 棵维护 $[1,i]$ 学生的奖金（排序后），记录区间和以及区间数的个数。