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/

Posted by xiaodao
Category: POJ