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/
