#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int tot=1, n, m;
int sum[(maxn << 5) + 10], rt[maxn + 10], ls[(maxn << 5) + 10],
rs[(maxn << 5) + 10];
int a[maxn + 10], ind[maxn + 10], len;
inline int getid(const int &val) {
return lower_bound(ind + 1, ind + len + 1, val) - ind;
}
int update(int k, int l, int r, int root) { // 插入操作
int dir = ++tot;
ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
if (l == r) return dir;
int mid = l + r >> 1;
if (k <= mid)
ls[dir] = update(k, l, mid, ls[dir]);
else
rs[dir] = update(k, mid + 1, r, rs[dir]);
return dir;
}
int query(int u, int v, int l, int r, int k) { // 查询操作
int mid = l + r >> 1,
x = sum[ls[v]] - sum[ls[u]]; // 通过区间减法得到左儿子的信息
if (l == r) return l;
if (k <= x) // 说明在左儿子中
return query(ls[u], ls[v], l, mid, k);
else // 说明在右儿子中
return query(rs[u], rs[v], mid + 1, r, k - x);
}
inline void init() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
memcpy(ind, a, sizeof ind);
sort(ind + 1, ind + n + 1);
len = unique(ind + 1, ind + n + 1) - ind - 1;
rt[0] = 1;
for (int i = 1; i <= n; ++i) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}
int l, r, k;
inline void work() {
while (m--) {
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", ind[query(rt[l - 1], rt[r], 1, len, k)]); // 回答询问
}
}
int main() {
init();
work();
return 0;
}
把build函数删了,一样过了,主席树不用建树的吗?