描述 Description

ForeverBell不仅精通破译密码,更是我军的重要代码编写者(至于什么代码,自己想吧).战争的日子是无聊的,有一天,ForeverBell找到了treeboy,出了一个极其简单的问题:给定一段序列,找出这段数列中第k小的数.
为了照顾treeboy的超弱语文水平,ForeverBell极其耐心地解释了这个问题:给定一个整数数列num[1…n],序列中的每个数字都不相同.你需要回答一组格式为Q(i,j,k)的查询,表示”在num[i…j]中第k小的数是多少”.
由于treeboy不仅语文差,而且代码能力巨弱,所以再次找到了你,请你编写一个程序,应对ForeverBell的询问.
输入格式 InputFormat

第一行两个整数n,m.分别是数列的总长度和ForeverBell询问的次数. 1≤n≤100 000，1≤m≤5 000
第二行有n个数，代表数列的元素，所有数都不相同，而且不会超过10^9 。
接下来有m行，每行三个整数i、j、k，代表一次查询，i、j、k满足：1≤i≤j≤n， 1≤k≤j-i+1。
输出格式 OutputFormat

一共m行.第i行表示第i次询问的答案.
样例输入 SampleInput [复制数据]

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
样例输出 SampleOutput [复制数据]

5
6
3

这道题算是模版题吧，看了一下说是什么划分树，不懂。。。然后就百度了一下，然后发现百度上的模版直接就能用了，然后就学习了一下，然后我打算把百度百科上的说明copy下来这里方便查阅。。。

划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内）序列区间的第k大值

1简介

查找整序列的第k大值往往采用快速查找法。然而此方法会破坏原序列，并且需要O(n)的时间复杂度。抑或使用二叉平衡树进行维护，此方法每次查找时间复杂度仅为O(logn)。然而此方法丢失了原序列的顺序信息，无法查找出某区间内的第k大值。

划分树的基本思想就是对于某个区间，把它划分成两个子区间，左边区间的数小于右边区间的数。查找的时候通过记录进入左子树的数的个数，确定下一个查找区间，最后范围缩小到1，就找到了。

2建树

建树的过程比较简单，对于区间[l,r]，首先通过对原数组的排序找到这个区间的中位数a[mid]，小于a[mid]的数划入他的左子树[l,mid-1]，大于它的划入右子树[mid,r]。同时，对于第i个数，记录在[l,i]区间内有多少数被划入左子树。最后，对它的左子树区间[l,mid-1]和右子树区间[mid,r]递归的继续建树就可以了。
建树的时候要注意对于被分到同一子树的元素，元素间的相对位置不能改变。

3查找

查找的过程中主要问题就是确定将要查找的区间。这个问题有些麻烦。

先看一下查找过程tree_find.他的定义如下：

查找深度为h，在大区间[st,ed]中找小区间[s,e]中的第k元素。
再看看他是如何工作的。我们的想法是，先判断[s,e]中第k元素在[st,ed]的哪个子树中，然后找出对应的小区间和k，递归的进行查找，直到小区间的s=e为止。
那如何解决这个问题呢？这时候前面记录的进入左子树的元素个数就派上用场了。通过之前的记录可以知道，在区间[st,s-1]中有el[h,s-1]进入左子树，记它为l。同理区间[st,e]中有el[h,e]个数进去左子树，记它为r。所以，我们知道区间小区间[s,e]中有(r-l)个数进入左子树。那么如果(r-l)>=k，那么就在左子树中继续查找，否则就在右子树中继续查找。
接着解决查找的小区间的问题。
如果接下来要查找的是左子树，那么小区间应该是[st+([st,s-1]区间进入左子树的个数),st+([st,e]区间内进入左子树的个数)-1]，即区间[st+l,st+r-1]。显然，这里k不用变。
如果接下来要查找的是右子树，那么小区间应该是[mid+([st,s-1]区间中进入右子树的个数),mid+([st,e]区间进入右子树的个数)-1]。即区间[mid+(s-st-l),mid+(e-st-r)]。显然，这里k要减去区间里已经进入左子树的个数，即k变为k-(r-l)。
于是递归继续查找直到s=e即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define N 100500
#define MID ((l+r)>>1)

int a[N], s[N], t[20][N], num[20][N], n, m;

void Build(int c, int l, int r) {
    int lm = MID-l+1, lp = l, rp = MID+1;
    for (int i = l; i <= MID; i++)
        lm -= s[i] < s[MID];
    for (int i = l; i <= r; i++) {
        if (i == l)
            num[c][i] = 0;
        else
            num[c][i] = num[c][i-1];
        if (t[c][i] == s[MID]) {
            if (lm) {
                lm--;
                num[c][i]++;
                t[c+1][lp++] = t[c][i];
            } else {
                t[c+1][rp++] = t[c][i];
            }
        } else if (t[c][i] < s[MID]) {
            num[c][i]++;
            t[c+1][lp++] = t[c][i];
        } else {
            t[c+1][rp++] = t[c][i];
        }
    }
    if (l < r) {
        Build(c+1, l, MID);
        Build(c+1, MID+1, r);
    }
}

int Query(int c, int l, int r, int ql, int qr, int k) {
    if (l == r)
        return t[c][l];
    int s, ss;
    if (l == ql) {
        s = 0;
        ss = num[c][qr];
    } else {
        s = num[c][ql-1];
        ss = num[c][qr] - num[c][ql-1];
    }
    if (k <= ss)
        return Query(c+1, l, MID, l+s, l+s+ss-1, k);
    else
        return Query(c+1, MID+1, r, MID+1+ql-l-s, MID+1+qr-l-s-ss, k-ss);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = t[0][i] = a[i];
    }
    sort(s+1, s+1+n);
    Build(0, 1, n);
    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", Query(0, 1, n, l, r, k));
    }
    return 0;
}