记录编号	600088	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	3.222 s
提交时间	2025-04-15 20:05:55	内存使用	35.44 MiB

#include <cstdio>

const int MAXV = 1e9;
const int MAXN = 2e5 + 10;

struct NODE {
    int ls, rs;
    int sum;
} node[MAXN * 40];

int nodeNum;
void Insert(int rootBefore, int &root, int lt, int rt, int val) {
    root = ++nodeNum;
    node[root] = node[rootBefore];
    if (lt == rt) {
        node[root].sum += 1;
        return ;
    }
    int mid = lt + ((rt - lt) >> 1);
    if (val <= mid) {
        Insert(node[rootBefore].ls, node[root].ls, lt, mid, val);
    } else {
        Insert(node[rootBefore].rs, node[root].rs, mid + 1, rt, val);
    }
    node[root].sum = node[node[root].ls].sum + node[node[root].rs].sum;
}

int GetK(int rootBefore, int root, int lt, int rt, int k) {
    if (lt == rt) {
        return lt;
    }
    int mid = lt + ((rt - lt) >> 1);
    int x = node[node[root].ls].sum - node[node[rootBefore].ls].sum;
    if (x >= k) {
        return GetK(node[rootBefore].ls, node[root].ls, lt, mid, k);
    } else {
        return GetK(node[rootBefore].rs, node[root].rs, mid + 1, rt, k - x);
    }
}

int n, m;
int a[MAXN];
int root[MAXN];

int main() {
	freopen("kthnumber.in", "r", stdin);
	freopen("kthnumber.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        Insert(root[i - 1], root[i], -MAXV, MAXV, a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int l, r, k;
        scanf("%d %d %d", &l, &r, &k);
        printf("%d\n", GetK(root[l - 1], root[r], -MAXV, MAXV, k));
    }
    return 0;
}