在acwing上交一直差两个点卡不过去……

奇偶优化什么都加了依旧不行

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
long long a[100010];
typedef long long ll;
__gnu_pbds::tree<ll,__gnu_pbds::null_type,std::less<ll>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>s;
pair<pair<long long,long long>,pair<long long,int > > t[100003];
long long ans[100003];
long long T;
long long n,m;
bool cmp(pair<pair<long long,int>,pair<long long,int> > a,pair<pair<long long,long long>,pair<long long,int> > b){
	return (!((a.first.first-1)/T+1)%2)^(a.first.second<b.first.second);
}
inline long long mo_algorithm(register long long l1,long long r1,long long l2,long long r2,long long k){
	for(register long long i=r1+1;i<=r2;i++){
		s.insert(a[i]);
	}	
	for(register long long i=l1;i<l2;i++){
		s.erase(a[i]);
	}
	for(register long long i=l1-1;i>=l2;i--){
	s.insert(a[i]);
	}
	for(register long long i=r1;i>r2;i--){
	s.erase(a[i]);
	}
	return *s.find_by_order(k-1);
}
inline void solve(){
	/*for(register long long i=1;i<=m;i++)
	{
		cout<<t[i].first.first<<' '<<t[i].first.second<<' '<<t[i].second.first<<' '<<t[i].second.second<<endl;
	}*/
	for(register long long i=t[1].first.first;i<=t[1].first.second;i++){
		s.insert(a[i]);
	}
	ans[t[1].second.second]=*s.find_by_order(t[1].second.first-1);
	for(register long long i=2;i<=m;i++){
		
		ans[t[i].second.second]=mo_algorithm(t[i-1].first.first,t[i-1].first.second,t[i].first.first,t[i].first.second,t[i].second.first);
	}
}
inline long long read()
{
    register long long x=0,f=0;register char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}
int main()
{
    cin>>n>>m;
	T=sqrt(sqrt(m));
	for(register long long i=1;i<=n;i++)
	{
		a[i]=read();
		a[i]+=1e9;
	}
	for(register long long i=1;i<=m;i++)
	{
		long long x=read(),y=read(),z=read();
		t[i]={{x,y},{z,i}};
	}		
	
	sort(t+1,t+m+1);	
	long long pre=0,temp=T;
	for(register long long i=1;i<=m;i++)
	{
		if(t[i].first.first>temp)
		{
		sort(t+pre+1,t+i+1,cmp);
		temp=T*((t[i].first.first-1)/T+1);
		pre=i;
		}
	}
	sort(t+pre+1,t+m+1,cmp);
	solve();
	for(register long long i=1;i<=m;i++) printf("%lld\n",ans[i]-1ll*1000000000);
}