某岛

… : "…アッカリ～ン . .. . " .. .

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