某岛

… : "…アッカリ~ン . .. . " .. .
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) 回答询问的方法,其实完全是一个东西。

(值得注意的是左边的 “线段树” 建立起来的方式,实际上是反向,从叶子结点开始做归并树。。。
(可见归并树与划分树之间的种种联系。。同时也再次让我们看到了划分树中,用辅助数组决定递归方向的同时缩小询问区间的思想是多么精髓啊!。。。

主席树


const int N = int(1e5) + 9, M = int(1e5) + 9, NN = int(5e7) + 9;

int l[NN], r[NN], c[NN], total;
int Tn;

#define lx l[x]
#define rx r[x]
#define ly l[y]
#define ry r[y]
#define cx c[x]
#define cy c[y]
#define ml ((ll+rr)>>1)
#define mr (ml+1)
#define lc lx, ll, ml
#define rc rx, mr, rr

int Insert(int y, int p, int d){
    
    int x = ++total, root = x;
    
    c[x] = c[y] + d; int ll = 0, rr = Tn;
    
    while (ll < rr){
        if (p < mr){
            lx = ++total, rx = ry;
            x = lx, y = ly, rr = ml;
        }
        else {
            lx = ly, rx = ++total;
            x = rx, y = ry, ll = mr;
        }
        c[x] = c[y] + d;
    }
    
    return root;
}

int A[N], S[N];
int n, m;

int Query(int ll, int rr, int k ) {
    
    --ll; int x = S[rr], y = S[ll];
    ll = 0, rr = Tn;
    
    while (ll < rr){
        int d = c[lx] - c[ly];
        if (d >= k){
            x = lx, y = ly;
            rr = ml;
        }
        else {
            x = rx, y = ry;
            k -= d, ll = mr;
        }
    }
    return ll;
}


int main() {
    
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
#ifndef ONLINE_JUDGE
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    
    RD(n, m);
    
    VI P; CLR(P); REP_1(i, n) P.PB(RDD(A[i]));
    UNQ(P); Tn = SZ(P)-1;
    REP_1(i, n) S[i] = Insert(S[i-1], LBD(P, A[i]), 1);
    
    
    DO(m) {
        int a,b,k;RD(a,b,k);
        OT(P[Query(a,b,k)]);
    }
}

const int N = int(1e5) + 9, M = int(1e5) + 9, NN = int(5e7) + 9;

int l[NN], r[NN], c[NN], total;
int Tn;

#define lx l[x]
#define rx r[x]
#define ly l[y]
#define ry r[y]
#define cx c[x]
#define cy c[y]
#define ml ((ll+rr)>>1)
#define mr (ml+1)
#define lc lx, ll, ml
#define rc rx, mr, rr

int Insert(int y, int ll, int rr, int p, int d) {
    int x = ++total; c[x] = c[y] + d;
    if (ll < rr) {
        if (p < mr) {
            lx = Insert(ly, ll, ml, p, d), rx = ry;
        } else {
            lx = ly, rx = Insert(ry, mr, rr, p, d);
        }
    }
    return x;
}

int Select(int x, int y, int ll, int rr, int k) {
    if (ll == rr) return ll;
    int d = c[lx] - c[ly];
    return k <= d ? Select(lx, ly, ll, ml, k) : Select(rx, ry, mr, rr, k-d);
}

int A[N], S[N]; VI P;
int n, m;

int Query(int l, int r, int k) {
    return P[Select(S[r], S[l-1], 0, Tn, k)];
}

int main() {
    
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
#ifndef ONLINE_JUDGE
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    
    RD(n, m); REP_1(i, n) P.PB(RDD(A[i]));
    UNQ(P); Tn = SZ(P)-1;
    REP_1(i, n) S[i] = Insert(S[i-1], 0, Tn, LBD(P, A[i]), 1);
    
    
    DO(m) {
        int a,b,k;RD(a,b,k);
        OT(Query(a,b,k));
    }
}

External link:

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