WA1,TLE8 qiuzhu

#include<bits/stdc++.h>
using namespace std;
struct zxs
{
	int l,r,l1,r1,z,xz;
}t[1000001],root[400001];
int a[200001],aa[200001],cnt,aaaa[200001];
map<int,int>q;
void inline js(int k,int l,int r)
{
	t[k].l=l,t[k].r=r;
	if(l==r)
	{
	t[k].xz=aa[aaaa[l]];
	return;
	}
	t[k].l1=cnt+1;
	js(++cnt,l,(l+r)/2);
	t[k].r1=cnt+1;
	js(++cnt,(l+r)/2+1,r);
}
void inline js2(int xz,int yx,int j,int i)
{
	t[xz].l=t[yx].l,t[xz].r=t[yx].r;
	t[xz].z++;
	if(t[xz].l==t[xz].r)
	{
	t[xz].xz=aa[aaaa[i]];
	return;
    }
	
	if(j>t[t[yx].l1].r)
	{
		t[xz].l1=t[yx].l1;
		t[xz].r1=++cnt;
		js2(cnt,t[yx].r1,j-t[t[yx].l1].r,i);
	}
	else
	{
		t[xz].r1=t[yx].r1;
		t[xz].l1=++cnt;
		js2(cnt,t[yx].l1,j,i);
	}
}
int inline cx(int a,int b,int c)
{
	if(t[b].l1==0)
	return t[a].xz;
	if(c>t[t[b].l1].z-t[t[a].l1].z)
	{
		return cx(t[a].r1,t[b].r1,c-t[t[b].l1].z+t[t[a].l1].z);
	}
	else
	{
		return cx(t[a].l1,t[b].l1,c);
	}
}
int main()
{
	int n,m;
	cin>>n;
	cin>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>aa[i];
		q[aa[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		a[q.begin()->second]=i;
		aaaa[i]=q.begin()->second;
		q.erase(q.begin());
	}
	js(++cnt,1,n);
	root[0].l1=t[1].l1;
	root[0].r1=t[1].r1;
	int aaa;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>(1+n)/2)
		{
			aaa=root[i-1].r1;
			root[i].l1=root[i-1].l1;
			root[i].r1=cnt+1;
			js2(++cnt,aaa,a[i],i);
		}
		else
		{
			aaa=root[i-1].l1;
			root[i].r1=root[i-1].r1;
			root[i].l1=cnt+1;
			js2(++cnt,aaa,a[i],i);
		}
	}
	for(int i=1;i<=m;i++)
	{
		int aaa,bbb,ccc;
	    cin>>aaa>>bbb>>ccc;
		if(ccc>t[root[bbb].l1].z-t[root[aaa-1].l1].z)
		{
			cout<<cx(root[aaa-1].r1,root[bbb].r1,ccc-t[root[bbb].l1].z+t[root[aaa-1].l1].z)<<endl;
		}
		else
		{
			cout<<cx(root[aaa-1].l1,root[bbb].l1,ccc)<<endl;
		}
	}
}