0pts:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sum(x) tr[x].sum
#define ls(x) (tr[x].lc)
#define rs(x) (tr[x].rc)
#define lazy(x) (tr[x].lazy)
const int N = 2e5+5;
struct node{
	int lc, rc;
	int sum;
}tr[N << 5];
int cnt;
int n, q;
int root[N];
int a[N];
int b[N];
int newnode(int x){
	tr[++cnt] = tr[x];
	return cnt;
}
void build(int &k, int l, int r){
	k = ++cnt;
	if (l == r){
		sum(k) = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(k), l, mid);
	build(rs(k), mid + 1, r);
}
void modify(int &k, int pre, int l, int r, int pos){
	k = ++cnt;
	sum(k) = sum(pre) + 1; //
	ls(k) = ls(pre);
	rs(k) = rs(pre);
	if (l == r){
		sum(k)++;
		return;
	}	
	int mid = (l + r) >> 1;
	if (pos <= mid) modify(ls(k), ls(pre), l, mid, pos);
	else modify(rs(k), rs(pre), mid + 1, r, pos);
	//sum(k) = sum(ls(k)) + sum(rs(k));
}
int query(int u, int v, int l, int r, int k){
	if (l >= r) return l;
	int x = sum(ls(v)) - sum(ls(u));
	int mid = (l + r) >> 1;
	if (x >= k) return query(ls(u), ls(v), l, mid, k);
	else return query(rs(u), rs(v), mid + 1, r, k - x);
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	int m = unique(b + 1, b + 1 + n) - b - 1;
	build(root[0], 1, n);
	for (int i = 1;i <= n;i++){
		int t = lower_bound(b + 1, b + 1 + m, a[i]) - b;
		modify(root[i], root[i - 1], 1, n, t);
	}
	while (q--){
		int l, r, k;
		cin >> l >> r >> k;
		int tmp = query(root[l - 1], root[r], 1, m, k);
		cout << b[tmp] << '\n';
	}
	return 0;
} 

20pts:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sum(x) tr[x].sum
#define ls(x) (tr[x].lc)
#define rs(x) (tr[x].rc)
#define lazy(x) (tr[x].lazy)
const int N = 2e5+5;
struct node{
	int lc, rc;
	int sum;
}tr[N << 5];
int cnt;
int n, q;
int root[N];
int a[N];
int b[N];
int newnode(int x){
	tr[++cnt] = tr[x];
	return cnt;
}
void build(int &k, int l, int r){
	k = ++cnt;
	if (l == r){
		sum(k) = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(k), l, mid);
	build(rs(k), mid + 1, r);
}
void modify(int &k, int pre, int l, int r, int pos){
	k = ++cnt;
	sum(k) = sum(pre); //
	ls(k) = ls(pre);
	rs(k) = rs(pre);
	if (l == r){
		sum(k)++;
		return;
	}	
	int mid = (l + r) >> 1;
	if (pos <= mid) modify(ls(k), ls(pre), l, mid, pos);
	else modify(rs(k), rs(pre), mid + 1, r, pos);
	sum(k) = sum(ls(k)) + sum(rs(k)); //
}
int query(int u, int v, int l, int r, int k){
	if (l >= r) return l;
	int x = sum(ls(v)) - sum(ls(u));
	int mid = (l + r) >> 1;
	if (x >= k) return query(ls(u), ls(v), l, mid, k);
	else return query(rs(u), rs(v), mid + 1, r, k - x);
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	int m = unique(b + 1, b + 1 + n) - b - 1;
	build(root[0], 1, n);
	for (int i = 1;i <= n;i++){
		int t = lower_bound(b + 1, b + 1 + m, a[i]) - b;
		modify(root[i], root[i - 1], 1, n, t);
	}
	while (q--){
		int l, r, k;
		cin >> l >> r >> k;
		int tmp = query(root[l - 1], root[r], 1, m, k);
		cout << b[tmp] << '\n';
	}
	return 0;
}