BZOJ 1901 Zju2112 Dynamic Rankings


题目链接: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)\) 的

详见代码:

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1901 Zju2112 Dynamic Rankings


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,