某島

… : "…アッカリ~ン . .. . " .. .
July 17, 2011

POJ 2104. K-th Number

Brief description:

給定一組區間,每次詢問 [a, b] 區間內第 k 小的數。
.. .

Analysis:

———— UPD ——————
主席樹
劃分樹

… 區間 k 小數問題,這類問題引出的演算法很多,互相之間都有聯繫,同時問題本身也有諸多擴展和變形,必須做總結。
首先,坊間流傳比較多的做法是歸併樹和劃分樹。

以 A = { 1, 7, 2, 5, 8, 3, 4, 6 } 為例,下面給出圖示:

[1  2  3  4  5  6  7  8]    [1  7  2  5  8  3  4  6]   root
[1  2  5  7][3  4  7  8]    [1  2  3  4][7  5  8  6]
[1  7][2  5][3  8][4  6]    [1  2][3  4][5  6][7  8]
[1][7][2][5][8][3][4][6]    [1][2][3][4][5][6][7][8]   leaf
	歸併樹			     劃分樹

像這樣把歸併排序 (Merge Sort) 中,
的中間過程記錄下來的話,就得到了歸併樹。。(對應的、將快速排序 (Quick Sort) 的中間過程記錄下來,就得到了劃分樹。。

對於歸併樹,容易回答 x 在當前區間中的排名,因而可以設計一個給予二分答案的演算法。
對於詢問 ([a, b], k),具體做法是現在樹上找到所有組成 [a, b] 的區間,之後得到 x 在所有這些區間中的排名並和 k 進行比較。
總的時間複雜度是 O(nlog^3n)。。。

而對於劃分樹,可以直接完成上述詢問不需要二分答案,方法是再劃分樹的基礎上建立一個輔助樹 (Auxiliary Tree)。
T[lv][i] 記錄從區間開始到第 i 個位置結束時,有多少數被劃分到了左邊。。

這樣具體是對於詢問 ([a, b], k),可以確定最終答案是在左子樹還是在右子樹內,
同時根據 Auxiliary Tree 中存儲的信息,進一步縮小區間 [a, b]。
時間複雜度只有 O(nlogn)。。。

(代碼 →這裡

//}/* .................................................................................................................................. */

const int N = int(1e5)+9, M = 18;
int A[N], T[M][N];
int n, m;

#define rt 0,0,n-1
#define lvv (lv+1)
#define ml (l+r>>1)
#define mr (ml+1)
#define lc lvv,l,ml
#define rc lvv,mr,r
#define t T[lv][i]

void Build(int lv, int l, int r){
    if (l == r) return;
    int ll = l, rr = mr; FOR_1(i, l, r){
        if (t <= A[ml]) T[lvv][ll++] = t; else T[lvv][rr++] = t;
        t = ll-l;
    }
    Build(lc), Build(rc);
}

/*
int Query(int lv, int l, int r, int a, int b, int k){
    if (l == r) return A[a];
    int ll = a == l ? 0 : T[lv][a-1], rr = T[lv][b];
    return rr - ll >= k ? Query(lc,l+ll,l+rr-1,k) : Query(rc,mr+a-l-ll,mr+b-l-rr,k+ll-rr);
}*/

inline int Query(int lv, int l, int r, int a, int b, int k){
    while (l < r){
        int ll = a == l ? 0 : T[lv][a-1], rr = T[lv][b];
        if (rr - ll >= k) a=l+ll,b=l+rr-1,r=ml;
        else a=mr+a-l-ll,b=mr+b-l-rr,k-=rr-ll,l = mr;
        ++lv;
    }
    return A[a];
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, m); REP(i, n) T[0][i] = RDD(A[i]); sort(A,A+n);
    Build(rt);int a,b,k;DO(m){
        RD(a,b,k);--a,--b;
        OT(Query(rt,a,b,k));
    }
}
[1  7  2  5  8  3  4  6]   [1  1  2  2  2  3  4  4] root
[1  2  3  4][7  5  8  6]   [1  2  2  2][0  1  1  2]
[1  2][3  4][5  6][7  8]   [1  1][1  1][1  1][1  1]
[1][2][3][4][5][6][7][8]    ——————————————————————  leaf
	劃分樹			   對應輔助樹

注意通常我們只需要 Auxiliary Tree,而不需要劃分樹,為了節約空間開銷,我們只需要保存其 Auxiliary Tree 就好。
另外注意到對於葉子節點,輔助樹是沒有定義的,上面的程序中在劃分樹的每個非葉子結點,
在完成了對應的建樹時刻的功能後,都被對應的 Auxiliary Tree 的結點覆蓋了。
(注意所有葉子結點是沒有被覆蓋的。。。在詢問的到葉子結點的時候,也可以返回 T[lv][l] 。。 )

歸併樹代碼移步 →這裡 。。。
(歸併樹思維複雜度雖然要低於劃分樹。。但是程序要難寫多了。。)

—————————— UPD:
下面介紹 xiaodai 學長教我的 O(nlog^2n) 演算法。。。對 A 數組的值域,建立線段樹。。(所以先要排序離散化。。。
線段樹的每個結點,保存一個有序數組,存儲 A 數組中,所有在這個值域的數的下標。。

這樣對於每個詢問 ([a, b], k),從線段樹的根節點開始,每次根據左子樹下標分布在 [a, b] 區間中數字的個數,
決定向左子樹遞歸還是向右子樹遞歸。。。。
(這一步要二分查找,劃分樹里這一步是通過在輔助數組上直接做差得到的。。

.. 完整代碼。。)

[1  2  3  4  5  6  7  8]    [1  7  2  5  8  3  4  6]   root
[1  3  6  7][2  4  5  8]    [1  2  3  4][7  5  8  6]
[1  3][6  7][4  8][2  5]    [1  2][3  4][5  6][7  8]
[1][3][6][7][4][8][2][5]    [1][2][3][4][5][6][7][8]   leaf
        值域線段樹	              劃分樹	

我們發現這種 「線段樹」 其實對應劃分樹的 Pos 版本。(取位置。。。
因而也可以向劃分樹中那樣,建立 Auxiliary Tree,得到 O(logn) 回答詢問的方法,其實完全是一個東西。

(值得注意的是左邊的 「線段樹」 建立起來的方式,實際上是反向,從葉子結點開始做歸併樹。。。
(可見歸併樹與劃分樹之間的種種聯繫。。同時也再次讓我們看到了劃分樹中,用輔助數組決定遞歸方向的同時縮小詢問區間的思想是多麼精髓啊!。。。

External link:

http://poj.org/problem?id=2104
http://www.notonlysuccess.com/index.php/divide-tree/