[BZOJ 1901] Dynamic Rankings

树状数组套主席树。

考虑无修改求区间第 K 大的情况:因为主席树之间支持相加减,故可以维护一些包含 1~i 的线段树,计算它们的树前缀和,从而快速得到区间 [l, r] 中的第 K 大数。

考虑对于数的静态区间和与动态区间和的关系——前缀和与树状数组。

类似地,我们可以维护一个树状数组,但线段树记录的不再是前缀和,而是树状数组的辅助数组的值。

这样就能做到带修改的区间第 K 大值查询了。

Reference:

http://blog.csdn.net/u014664226/article/details/47839973

代码如下:

继续阅读[BZOJ 1901] Dynamic Rankings