可持久化线段树

可持久化线段树

对于每一个历史副本，观察到只有一条链上的信息发生了变化，于是每次操作可以只更新一条链，并产生 \(logn\) 个节点

P3919 【模板】可持久化线段树 1

直接建树即可

P3834 【模板】可持久化线段树 2

建一颗权值线段树，维护 \([1,i]\) 上每个排名的出现次数，询问 \([l,r]\) 上第k小的数时直接将 \([1,r]\) 减去 \([1,l-1]\)