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