RT

稳稳地过了。（大号）

最慢点400多ms

另：

树套树也可能过。

具体这份代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,a[200005],l,r,m,ls,rs,mid,k,c[200005],d[200005],qn;
vector<int> tree[200005],h[200005];
inline int read(){
    int x(0);
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
inline void write(int x){
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
void add(int x,int k){
	while(x<=n){
		tree[x].push_back(k);
		x+=x&-x;
	}
} 
int qry(int x,int k){
	int ans=0;
	while(x){
		ans+=lower_bound(tree[x].begin(),tree[x].end(),k)-tree[x].begin();
		x-=x&-x;
	}
	return ans;
} 
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		c[i]=a[i];
	}
	sort(c+1,c+n+1);
	qn=n;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(c+1,c+n+1,a[i])-c;
		d[i]=max(d[i-1],a[i]);
		h[a[i]].push_back(i);
	}
	for(int i=1;i<=qn;i++){
		for(int j=0;j<h[i].size();j++){
			add(h[i][j],i);
		}
	}
	for(int i=1;i<=m;i++){
		l=read(),r=read(),k=read();
		ls=k,rs=d[r]-(r-l+1)+k;
		while(ls<rs){
			mid=(ls+rs+1)>>1;
			if(qry(r,mid)-qry(l-1,mid)>=k){
				rs=mid-1;
			}
			else{
				ls=mid;
			}
		}
		write(c[ls]);
		printf("\n");
	}
	return 0;
}

最慢点 1.35 秒，第二慢点 1.32秒（这两点实现均为 1.2秒），其余全部 AC 。