K-th Number

Time Limit: 20000MS Memory Limit: 65536K
Case Time Limit: 2000MS

Description

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.

Input

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 109 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).

Output

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

Sample Input

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

Sample Output

5
6
3

Hint

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

题意：

就是给我们一些数字，然后给我们一个区间，问我们在这个区间里面第几大的是哪个数字。

思路：

主席树的模板题，只要写个主席树的板子就行了，我这里讲讲学主席树时候的不懂得地方。
1 在更新的时候对x有个引用，其实不难理解，实际上就是对新的线段的的更新，因为y是旧的线段树，新的线段树是在上一个线段树的基础上更新的，所以才有了引用用来更新新线段树。
2 还有就是在离散化的时候有个unique就是把重复都放在末尾，然后返回不重复的尾指针。
3 查询的时候就是找两个区间端点所对应的线段树就行了，然后再这里面查找第k大的值。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e+5 + 10;
struct NODE {
    int l;
    int r;
    int sum;
};
NODE T[maxn * 50];
int root[maxn] = {0}, a[maxn];
int cnt = 0;
vector<int> v;
int GetId(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void Updata(int l, int r, int &x, int y, int pos) {
    T[++cnt] = T[y];
    T[cnt].sum++;
    x = cnt;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (mid >= pos) Updata(l, mid, T[x].l, T[y].l, pos);
    else Updata(mid + 1, r, T[x].r, T[y].r, pos);
}
int Query(int l, int r, int x, int y, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int sum = T[T[y].l].sum - T[T[x].l].sum;
    if (sum >= k) return Query(l, mid, T[x].l, T[y].l, k);
    else return Query(mid + 1, r, T[x].r, T[y].r, k - sum);
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; i++) Updata(1, n, root[i], root[i - 1], GetId(a[i]));
    while (m--) {
        int x, y, k;
        scanf("%d %d %d", &x, &y, &k);
        printf("%d\n", v[Query(1, n, root[x - 1], root[y], k) - 1]);
    }
    return 0;
}