某岛

… : "…アッカリ~ン . .. . " .. .
June 20, 2012

ZOJ 2112. Dynamic Rankings

Brief description:

给定一个长度为 N 的已知序列 A[i] (1≤i≤N),要求动态维护 M 次以下操作:
1、Q a b k 查询 A[a], A[a+1], A[a+2], …, A[b] (1≤a≤b≤N) 中,第 k 小的数。(Start From 1 …
2、C x y 修改 A[x] 的值为 y。
( .. N ≤ 50, 000 .. M ≤ 10, 000 .. 保证 A[i] 在任何中间时刻的绝对值都不超过 10^9 ..)

Analysis:

解决这个问题,需要用到“树套树”。建立一棵线段树,维护 N 的节点的所有区间,每个线段树节点上有一个平衡树,用来维护当前区间内所有数的动态排名。很显然,每个线段树节点上的平衡树,都是这个线段树节点的两个子节点的平衡树的合并。由于我们无法实现高效的平衡树合并,只好用这种以空间换时间的方法。
—— http://www.byvoid.com/blog/zju-2112/

当然这样做法就很明确了,(树状数组套平衡树思想也类似。)
对于查询操作 Q a b k,由于无法对线段树上高效的直接完成询问,
只有采取二分答案的方法,这个过程也可以先预处理把所有区间找到。

注意,对于询问关键字为 v 的结点的 Rank 值,很可能没有关键字为 x 的结点,或者有很多关键字为 x 的结点。。
(这里即便是进行预处理,进行离散化的二分答案,仍然有可能出现单个子树上不存在 x 结点的情况。)
也就是说得到的 Rank 值应该是一个区间,这里我们返回第一个大于等于 x 的结点。(upper_bound … )

这样设计后先把外部二分答案的过程确定下来:
如果 f(x) > k,那么当前的答案一定是不满足条件的,r = x – 1;
如果 f(x) <= k,那么最后的答案至少 >= x, l = x;

...
        RC(cmd); if (cmd =='Q'){
            RD(a, b, k); --k; int l = 0, r = INF;
            while (l < r){
                _x = (l + r + 1) >> 1;
                if (f() > k) r = _x - 1;
                else l = _x;
            }
            OT(l);
        }
...

A. 线段树套 Splay
B. 树状数组套 Splay

Further discuss:

但是这些写法都弱爆了。。。下一节详细介绍主席树。。。
先贴个 Seter 的代码膜拜一下。。。
(Seter 不仅缩代码。。而且还缩内存。。。Orz)。。。。

Seter’s 主席树

External link:

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112
http://www.lydsy.com/JudgeOnline/problem.php?id=1901

http://seter.is-programmer.com/posts/31907.html