10ps,主席树，大佬求助，玄关(AC第一个·)

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e7 +5;

struct qq{
	
	int sum,l,r;
	
}tr[N];

int n,m,a[N],root[N],b[N],cnt,ans,su; 

void build (int &x,int l,int r) {
	
	x = ++ cnt;
	tr[x].l = l;
	tr[x].r = r;
	
	if (l == r) {
		return ;
	}
	
	int mid = (l + r) >> 1;
	
	build (tr[x].l,l,mid);
	build (tr[x].r,mid + 1,r);
}

int insert (int x,int l,int r,int k) {
	int u = ++ cnt;
	tr[u].l = tr[x].l;
	tr[u].r = tr[x].r;
	tr[u].sum = tr[x].sum + 1;
	
	int mid = (l + r) >> 1;
	
	if (l == r) return u;
	
	if (su <= mid) {
		tr[u].l = insert(tr[x].l,l,mid,k);
	} else {
	//	su -= tr[u].sum;
		tr[u].r = insert(tr[x].r,mid + 1,r,k);
	}
	return u;
}

int query (int u,int v,int l,int r,int k) {
	
	int x = tr[tr[u].l].sum - tr[tr[v].l].sum;
	
	if (l == r) return l;
	
	int mid = (l + r) >> 1;
//	if (k == tr[tr[u].l].sum + 1) return u;
	if (k <= x) {
		ans = query(tr[u].l,tr[v].l,l,mid,k);
	} else {
		ans = query(tr[u].r,tr[v].r,mid + 1,r,k - x);
	}
	return ans;
}

signed main () {
	
	cin >> n >> m;
	
	for (int i = 1;i <= n;i ++) cin >> a[i],b[i] = a[i];
	
	
	sort (b + 1,b + n + 1);
	int len = unique (b + 1,b + n + 1) - b - 1;
	build (root[0],1,len);
	for (int i = 1;i <= n;i ++) {
		su = lower_bound(b + 1,b + len + 1,a[i]) - b;
		root[i] = insert (root[i - 1],1,len,su);
	}
	
	for (int i = 1,l,r,k;i <= m;i ++) {
		
		cin >> l >> r >> k;
		
		int res = query (root[r],root[l - 1],l,r,k);
		cout << a[res] << '\n';
	}
	return 0;
}