防忘笔记吧
思想
- 权值线段树
- 可持久化，每个点都沿用上一个版本
- update: 怎么沿用的？每次只修改一条链，剩下的前部继承前面的，可以理解为直接引了一条边给当前树和之前的树。
POJ 2104 (区间第k大)
- 主席树
- 主席树树上递归二分找第k大即可
SPOJ 3267 (区间不同数个数)
- 相比于区间第k大，实在权值线段树上按照数字的大小插入，区间不同数个数是在每个位置插入
- 对应每个查询区间[l,r]，只要查询当前root[r]，这棵树上区间[l,r]的不同数字即可
- 故问题转化为对于每颗root[i]如何不重复统计每个数
- 每次只记录每个数最后出现的位置即可，即出现重复的就把在其上一次出现的位置在当前这棵树删掉即可。