//求第K的的值
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 typedef long long LL; 7 const int maxn = 1e5 + 10; 8 int n, m, cnt; 9 struct node { 10 int L, R, sum; 11 } tree[maxn * 20]; 12 struct value { 13 int x, id; 14 } val[maxn]; 15 int cmp(value v1, value v2) { 16 return v1.x < v2.x; 17 } 18 int root[maxn], RANK[maxn]; 19 void init() { 20 cnt = 1; 21 root[0] = 0; 22 tree[0].L = tree[0].R = tree[0].sum = 0; 23 } 24 void updata(int num, int &rt, int l, int r) { 25 tree[cnt++] = tree[rt]; 26 rt = cnt - 1; 27 tree[rt].sum++; 28 if (l == r) return ; 29 int mid = (l + r) >> 1; 30 if (num <= mid) updata(num, tree[rt].L, l, mid); 31 else updata(num, tree[rt].R, mid + 1, r); 32 } 33 int query(int i, int j, int k, int l, int r) { 34 int d = tree[tree[j].L].sum - tree[tree[i].L].sum; 35 if (l == r) return l; 36 int mid = (l + r) >> 1; 37 if (k <= d) return query(tree[i].L, tree[j].L, k, l, mid); 38 else return query(tree[i].R, tree[j].R, k - d, mid + 1, r) ; 39 } 40 int main() { 41 scanf("%d%d", &n, &m); 42 for (int i = 1 ; i <= n ; i++) { 43 scanf("%d", &val[i].x); 44 val[i].id = i; 45 } 46 sort(val + 1, val + n + 1, cmp); 47 for (int i = 1 ; i <= n ; i++) 48 RANK[val[i].id] = i; 49 init(); 50 for (int i = 1 ; i <= n ; i++) { 51 root[i] = root[i - 1]; 52 updata(RANK[i], root[i], 1, n); 53 } 54 int left, right, k; 55 for (int i = 1 ; i <= m ; i++) { 56 scanf("%d%d%d", &left, &right, &k); 57 printf("%d ", val[query(root[left - 1], root[right], k, 1, n)].x); 58 } 59 return 0; 60 }