|
|
|
|
|
#include <iostream>
|
|
|
|
|
|
#include <cstring>
|
|
|
|
|
|
#include <cstdlib>
|
|
|
|
|
|
#include <cstdio>
|
|
|
|
|
|
#include <algorithm>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
|
|
|
|
|
|
const int N = 100010, M = 50010;
|
|
|
|
|
|
|
|
|
|
|
|
//快读
|
|
|
|
|
|
int read() {
|
|
|
|
|
|
int x = 0, f = 1;
|
|
|
|
|
|
char ch = getchar();
|
|
|
|
|
|
while (ch < '0' || ch > '9') {
|
|
|
|
|
|
if (ch == '-') f = -1;
|
|
|
|
|
|
ch = getchar();
|
|
|
|
|
|
}
|
|
|
|
|
|
while (ch >= '0' && ch <= '9') {
|
|
|
|
|
|
x = (x << 3) + (x << 1) + (ch ^ 48);
|
|
|
|
|
|
ch = getchar();
|
|
|
|
|
|
}
|
|
|
|
|
|
return x * f;
|
|
|
|
|
|
}
|
|
|
|
|
|
int n, m;
|
|
|
|
|
|
|
|
|
|
|
|
struct A {
|
|
|
|
|
|
int id, x;
|
|
|
|
|
|
const bool operator<(const A &t) const {
|
|
|
|
|
|
return x < t.x;
|
|
|
|
|
|
}
|
|
|
|
|
|
} a[N];
|
|
|
|
|
|
|
|
|
|
|
|
struct Q {
|
|
|
|
|
|
int id; //第几号查询
|
|
|
|
|
|
int l, r, k; //左右区间，第k小
|
|
|
|
|
|
} q[M];
|
|
|
|
|
|
|
|
|
|
|
|
//树状数组
|
|
|
|
|
|
int tr[N];
|
|
|
|
|
|
//查询x的个数和
|
|
|
|
|
|
int query(int x) {
|
|
|
|
|
|
int sum = 0;
|
|
|
|
|
|
for (; x; x -= x & -x) sum += tr[x];
|
|
|
|
|
|
return sum;
|
|
|
|
|
|
}
|
|
|
|
|
|
// x位置上增加c
|
|
|
|
|
|
void update(int x, int c) {
|
|
|
|
|
|
for (; x <= n; x += x & -x) tr[x] += c;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
//每个询问的答案数组
|
|
|
|
|
|
int ans[M];
|
|
|
|
|
|
|
|
|
|
|
|
//[l,r]:排序后数组上的区间
|
|
|
|
|
|
//[x,y]:询问集合的区间
|
|
|
|
|
|
void solve(int l, int r, int x, int y) {
|
|
|
|
|
|
if (x > y) return; //查询的子区间非法，返回
|
|
|
|
|
|
|
|
|
|
|
|
if (l == r) {
|
|
|
|
|
|
for (int i = x; i <= y; i++) ans[q[i].id] = a[l].x;
|
|
|
|
|
|
return;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int mid = (l + r) >> 1;
|
|
|
|
|
|
for (int i = l; i <= mid; i++) update(a[i].id, 1);
|
|
|
|
|
|
|
|
|
|
|
|
int i = x, j = y, t;
|
|
|
|
|
|
|
|
|
|
|
|
while (i <= j) {
|
|
|
|
|
|
while (i <= j && q[i].k <= query(q[i].r) - query(q[i].l - 1)) i++;
|
|
|
|
|
|
|
|
|
|
|
|
while (i <= j && q[j].k > (t = query(q[j].r) - query(q[j].l - 1))) {
|
|
|
|
|
|
q[j].k -= t;
|
|
|
|
|
|
j--;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
if (i < j)
|
|
|
|
|
|
swap(q[i], q[j]);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = l; i <= mid; i++) update(a[i].id, -1);
|
|
|
|
|
|
|
|
|
|
|
|
solve(l, mid, x, j), solve(mid + 1, r, i, y);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
n = read(), m = read();
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= n; i++) a[i].x = read(), a[i].id = i;
|
|
|
|
|
|
|
|
|
|
|
|
//查询请求
|
|
|
|
|
|
for (int i = 1; i <= m; i++) {
|
|
|
|
|
|
q[i].l = read(), q[i].r = read(), q[i].k = read();
|
|
|
|
|
|
q[i].id = i;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
sort(a + 1, a + 1 + n); //将原数组的二元组按值大小进行由小到大的排序，同步记录了每个数值对应的序号
|
|
|
|
|
|
|
|
|
|
|
|
//离线处理
|
|
|
|
|
|
//二分区间为[1,n] ,查询区间q[1]~q[m]???
|
|
|
|
|
|
solve(1, n, 1, m);
|
|
|
|
|
|
|
|
|
|
|
|
//输出每次询问的答案
|
|
|
|
|
|
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
|
|
|
|
|
|
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
