无旋Treap离线，样例过不去，调不大出来（

本人刚学离线，轻喷（

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
//#include<map>
#include<vector>
#include<math.h>
using namespace std;
#define int long long
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define repp(i,a,b) for(int i=a;i>=b;i--)
#define INF 1e9
#define ll long long
#define MAXN 1000006
const int _x[]={0,1,0,-1,0},_y[]={0,0,1,0,-1};
#define mem(a,n) memset(a,n,sizeof(a));
#define chkmax(a,b) a=a>b?a:b;
#define chkmin(a,b) a=a<b?a:b;
#include<set>
#include<stack>
#define lc tree[i].l
#define rc tree[i].r
int root,cnt;
struct FHQtree{
	int l,r;
	int size,key;
	int val;
}tree[MAXN*4];
void update(int i){
	tree[i].size=tree[lc].size+tree[rc].size+1;
}
int add(int i){
	tree[++cnt].val=i;
	tree[cnt].key=rand();
	tree[cnt].size=1;
	return cnt;
}
void split(int i,int k,int &l,int &r){
	if(!i){
		l=r=0;
		return;
	}
	if(tree[i].val<=k){
		l=i;
		split(rc,k,rc,r);
	}
	else{
		r=i;
		split(lc,k,l,lc);
	}
	update(i);
}
int merge(int l,int r){
	if(!l||!r){
		return l+r;
	}
	if(tree[l].key<=tree[r].key){
		tree[l].r=merge(tree[l].r,r);
		update(l);
		return l;
	}
	else if(tree[l].key>tree[r].key){
		tree[r].l=merge(l,tree[r].l);
		update(r);
		return r;
	}
}
int l,r,p;
void insert(int i){
	split(root,i,l,r);
	root=merge(merge(l,add(i)),r);
}
void pop(int i){
	split(root,i,l,p);
	split(l,i-1,l,r);
	r=merge(tree[r].l,tree[r].r);
	root=merge(merge(l,r),p);
}
int findrk(int x){
	split(root,x-1,l,r);
	int k=tree[l].size+1;
	root=merge(l,r);
	return k;
}
int findval(int i,int k){
	if(tree[lc].size+1==k){
		return tree[i].val;
	}
	if(tree[lc].size>=k){
		return findval(lc,k);
	}
	else{
		return findval(rc,k-tree[lc].size-1);
	}
}
int pre(int i){
	split(root,i-1,l,r);
	int k=findval(l,tree[l].size);
	root=merge(l,r);
	return k;
}
int back(int i){
	split(root,i,l,r);
	int k=findval(r,1);
	root=merge(l,r);
	return k;
}
int last,ans;
int n,m;
int a[MAXN*4];
struct Quest{
	int l,r,k,id;
}q[MAXN*4];
bool cmp(const Quest &q1,const Quest &q2){
	if(q1.l!=q2.l){
		return q1.l<q2.l;
	}
	return q1.r<q2.r;
}
int answer[MAXN*4];
int px=1,py=0;
signed main(){
	scanf("%lld%lld",&n,&m);
	forr(i,1,n){
		scanf("%lld",&a[i]);
	}
	forr(i,1,m){
		scanf("%lld%lld%lld",&q[i].l,&q[i].r,&q[i].k);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	forr(i,1,m){
		while(py<q[i].r){
			insert(a[++py]);
		}
		while(px<q[i].l){
			pop(a[px++]);
		}
		answer[q[i].id]=findval(root,q[i].k+1);
	}
	forr(i,1,m){
		printf("%lld\n",answer[i]);
	}
}