BZOJ 1901 Zju2112 Dynamic Rankings

发布于 2017-11-15  152 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1901

题意:单点修改(赋值),询问区间第 k 大。


如果没有修改操作就是主席树裸题了,有修改操作怎么办呢?

一个朴素的想法是暴力修改所有影响到的版本的信息,不过一个点修改影响了它的所有前缀,即\(O(n)\) 颗树,暴力的复杂度是\(O(nlog_n)\) 的,不能接受。

重点在于如何高效的修改前缀信息,发现树状数组可以很优雅的解决。于是我们用一个树状数组将所有版本的根串起来,每次修改跳一下 lowbit,修改经过的那些树即可。

这一步是\(O({log_n}^2)\) 的

询问操作如何处理呢?一样同步的在那\(log_n\) 棵树上爬即可了,复杂度也是\(O({log_n}^2)\) 的

详见代码:

 


一个非常弱的准退役OIER