[ZJ][歸併樹] a331. K-th Number＠Morris' Blog

2012-08-24 11:35:58| 人氣676| 回應0 | 上一篇 | 下一篇

[ZJ][歸併樹] a331. K-th Number

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

輸入說明：

The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 10⁹ by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

輸出說明：

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

範例輸入：

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

範例輸出：

5
6
3

提示：

出處：

Northeastern Europe 2004, Northern Subregion (管理：david942j)

轉載 http://hi.baidu.com/zhiqing110c/item/9cd539fa1d0127693c148556

1，建立归并树后我们得到了序列key[]的非降序排列，由于此时key[]内元素的rank是非递减的，因此key[]中属于指定区间[s,t]内的元素的rank也是非递减的，所以我们可以用二分法枚举key[]中的元素并求得它在[s,t]中的 rank值，直到该rank值和询问中的rank值相等；

2，那对于key[]中的某个元素val，如何求得它在指定区间[s,t]中的 rank？这就要利用到刚建好的归并树：我们可以利用类似线段树的 query[s,t]操作找到所有属于[s,t]的子区间，然后累加val分别在这些子区间内的rank，得到的就是val在区间[s,t]中的 rank，注意到这和合并排序的合并过程一致；

3，由于属于子区间的元素的排序结果已经记录下来，所以val在子区间内的rank可以通过二分法得到。
上面三步经过了三次二分操作（query也是种二分），于是每次询问的复杂度是O(log n * log n * log n)

#include <stdio.h>
typedef struct {
    int l, r;
} Node;
Node ST[262145];
int seg[20][100005];
int a[100005];
void build(int l, int r, int k, int depth) {
    ST[k].l = l, ST[k].r = r;
    if(l == r) {
        seg[depth][l] = a[l];
        return;
    }
    int m = (l+r)>>1;
    build(l, m, k<<1, depth+1);
    build(m+1, r, k<<1|1, depth+1);
    int idx1 = l, idx2 = m+1, top = l;
    while(idx1 <= m && idx2 <= r) {
        if(seg[depth+1][idx1] < seg[depth+1][idx2])
            seg[depth][top++] = seg[depth+1][idx1++];
        else
            seg[depth][top++] = seg[depth+1][idx2++];
    }
    while(idx1 <= m)    seg[depth][top++] = seg[depth+1][idx1++];
    while(idx2 <= r)    seg[depth][top++] = seg[depth+1][idx2++];
}
int find(int k, int dep, int val, int ql, int qr) {
    if(ql <= ST[k].l && ST[k].r <= qr) {
        int l = ST[k].l, r = ST[k].r;
        while(l < r) {
            int m = (l+r)>>1;
            if(seg[dep][m] < val)
                l = m+1;
            else
                r = m;
        }
        if(seg[dep][l] <= val)
            return l - ST[k].l+1;
        else
            return l - ST[k].l;
    }
    int res = 0;
    if(ql <= ST[k<<1].r)
        res += find(k<<1, dep+1, val, ql, qr);
    if(qr >= ST[k<<1|1].l)
        res += find(k<<1|1, dep+1, val, ql, qr);
    return res;
}
int main() {
    int n, m, ql, qr, k, i;
    while(scanf("%d %d", &n, &m) == 2) {
        for(i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        build(1, n, 1, 1);
        while(m--) {
            scanf("%d %d %d", &ql, &qr, &k);
            int l = 1, r = n;
            while(l < r) {
                int m = (l+r)>>1;
                if(find(1, 1, seg[1][m], ql, qr) < k)
                    l = m+1;
                else
                    r = m;
            }
            printf("%d\n", seg[1][l]);
        }
    }
    return 0;
}

我要檢舉

#a331#K-th Number

台長： Morris

您可能對以下文章有興趣

[ZJ][數學解] a534. IOI2008 Day2.1.花園問題

a094. NOI2003 Day1.1.木棒游戏

d887. 1.山脈種類(chain)

[ZJ][LCA] b237. CSAPC'09 迷宮任務

人氣(676) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][scc強連通元件][Tarjan算法] b201. F. 國家
此分類上一篇:[ZJ][模擬水] a349. 2. 指令解譯器

回應(0)