第一组数据：

input:

200 10
7209657 5715254 7484194 9245403 7946074 8376995 3639053 5577156 2180410 7346802 7626387 4149578 4031884 1507994 5003689 4596914 4488716 1492638 7054791 8542628 6570071 7174603 4869580 574985 9916054 1817585 9793206 5394049 577809 9751939 2687405 4712031 8738867 4511450 7325233 9436841 2412868 5023140 2919757 2196578 406775 8812258 2782365 51575 7438126 41726 4278992 2479093 5718890 3289713 43950 5668480 6709687 186496 1300388 7089033 3692040 5026776 8084278 9061484 9925903 8364216 8045835 3118926 1809148 8325526 7350791 2640984 7862022 3761442 8555301 6031411 8140901 1148346 5814309 6706863 4154026 9100633 9890849 7665077 5334496 7582790 5437893 6413334 1486072 8750940 9872563 7857680 9250804 2373472 2736403 1669179 7077419 4075022 9031937 2573700 1787932 2702408 1791921 9911253 4104675 374651 9182567 2861722 9683596 5180583 4392238 7633306 172552 1590281 3982180 266453 7460401 5712783 2436308 4062596 3958493 7399436 4338192 7458177 2200920 1472940 4613082 7185617 242413 3920050 1847944 7391352 5920283 3222429 4823159 3965059 1054445 1711964 7212940 418495 4807097 5332625 9729664 4443813 2333264 5070267 1208358 9520893 2449440 1074602 3007198 15356 4451438 8880248 3749369 3950409 53446 3563438 4515086 4092955 7714781 6739340 889271 4557059 504065 9064061 9799772 4858319 9452903 2839341 1182694 6321551 5905386 6044896 8645672 9652531 3971978 6079703 2848943 3792154 2550719 7867529 5493104 6565729 7723571 4921155 1738934 914123 9353601 6287556 9617724 8943543 8635011 9595908 2263756 969687 133403 3003915 32936 9960604 894425 4977425 3421245 7298157 
25 56 28
18 44 16
33 70 2
15 34 10
8 22 2
40 99 34
46 109 61
47 113 7
39 87 14
51 132 59

output:

8812258
5394049
43950
4869580
1507994
6031411
9872563
1300388
2919757
7458177

我的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,INF=1e9+10;
struct node{
	int l,r;
	int k,id;
}pr[N];
int n,m,cnt,root,sum,w[N],ans[N];
struct treap{
	int ls,rs;
	int key,data,size;
}tr[N];
int New(int x)
{
	tr[++cnt].ls=tr[cnt].rs=0;
	tr[cnt].key=x;
	tr[cnt].data=rand();
	tr[cnt].size=1;
	return cnt; 
}
void Push_up(int x)
{
	tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
void Build()
{
	New(-INF),New(INF);
	root=1,tr[1].rs=2;
	Push_up(root);
}
void zig(int &x)//拎左儿子
{
	int son=tr[x].ls;
	int temp=tr[son].rs;
	tr[son].rs=x;
	tr[x].ls=temp;
	x=son;
	Push_up(tr[x].rs),Push_up(x);
}
void zeg(int &x)
{
	int son=tr[x].rs;
	int temp=tr[son].ls;
	tr[son].ls=x;
	tr[x].rs=temp;
	x=son;
	Push_up(tr[x].ls),Push_up(x);
}
void Insert(int &x,int val)
{
	if(!x)
	{
		x=New(val);
		return ;
	}
	if(val<tr[x].key)
	{
		Insert(tr[x].ls,val);
		if(tr[tr[x].ls].data>tr[x].data)zig(x);
		Push_up(x); 
	}
	else
	{
		Insert(tr[x].rs,val);
		if(tr[tr[x].rs].data>tr[x].data)zeg(x);
		Push_up(x);
	}
}
void Remove(int &x,int val)
{
	if(!x)return ;
	if(val==tr[x].key)
	{
		if(tr[x].ls||tr[x].rs)
		{
			if(!tr[x].rs||tr[tr[x].ls].data>tr[tr[x].rs].data)zig(x),Remove(tr[x].rs,val);
			else zeg(x),Remove(tr[x].ls,val);
			Push_up(x);
		}
		else x=0;
		return ;
	}
	if(val<tr[x].key)Remove(tr[x].ls,val);
	else Remove(tr[x].rs,val);
	Push_up(x);
}
int getkey(int x,int rank)
{
	if(!x)return 0x3f3f3f3f;
	if(tr[tr[x].ls].size>=rank)return getkey(tr[x].ls,rank);
	else if(tr[tr[x].ls].size+1==rank)return tr[x].key;
	else return getkey(tr[x].rs,rank-tr[tr[x].ls].size-1);
}
bool cmp(node x,node y)
{
	if(x.l==y.l)return x.r<y.r;
	return x.l<y.l;
}
int main(void)
{
	freopen("std.in","r",stdin);
	
	Build();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		pr[++sum].l=a;
		pr[sum].r=b;
		pr[sum].k=c;
		pr[sum].id=i;
	}
	sort(pr+1,pr+sum+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(r<pr[i].r)Insert(root,w[++r]);
		while(l<pr[i].l)Remove(root,w[l++]);
		ans[pr[i].id]=getkey(root,pr[i].k+1);
	}
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<endl;
	return 0;
}