主席树

参考
可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。
一些数据结构,比如线段树或平衡树,他们一般是要么维护每个元素在原序列中的排列顺序,要么是维护每个元素的大小顺序,若是像二者兼得。。(反正我是觉得很。。)那么,这道题就想想主席树吧~