Brief description:
給定一組區間，每次詢問 [a, b] 區間內第 k 小的數。
.. .
Analysis:
… 區間 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/
