#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200010];
int b[200010]; 
int rt[200010];
int maxn;
int top;
struct TRE{
	int l,r;
	int ls,rs;
	int num;
}t[40000010];
void built(int l,int r,int p){
	t[p].l=l,t[p].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	t[p].ls=++top;
	built(l,mid,top);
	t[p].rs=++top;
	built(mid+1,r,top);
}
void add(int ps,int p,int a){
	t[p]=t[ps];
	t[p].num++;
	if(t[p].l==t[p].r) return;
	int mid=(t[p].l+t[p].r)>>1;
	if(a<=mid){
		t[p].ls=++top;
		add(t[ps].ls,top,a);
	}else{
		t[p].rs=++top;
		add(t[ps].rs,top,a);
	}
}

int sek(int l,int p,int k){
	if(t[p].l==t[p].r) return t[p].l;
	int ul=t[t[p].ls].num-t[t[l].ls].num;
	if(ul>=k) return sek(t[l].ls,t[p].ls,k);
	else return sek(t[l].rs,t[p].rs,k-ul);
}
int main(void){
//	freopen("P3834_3.in","r",stdin);
//	freopen("wrong.out","w",stdout);
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(a+1,a+1+n);
	maxn=unique(a+1,a+1+n)-a-1;
	built(0,maxn,++top);
	rt[0]=1; 
	for(int i=1;i<=n;i++){
		rt[i]=++top;
		int ul=lower_bound(a+1,a+1+n,b[i])-a;
		printf("%d\n",ul);
		add(rt[i-1],rt[i],ul);
	}
	int l,r,k;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",a[sek(rt[l-1],rt[r],k)]);
	}
	return 0;
}

萌新刚学主席树。
虽然代码很丑陋，但是并没有找到什么bug。。。
第3、4、5个点莫名WA掉？

求助。。。