做法：

$O(n\log^3n)$ 的树状数组套二分

我的大号经过一系列卡常，我已经成功把 $\# 9,\# 10$ 的时间降至1.22秒和1.21秒 （开 O2 ）。

现在就只差临门一脚了，谁能帮我调调啊！

Code：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,a[200005],l,r,m,ls,rs,mid,k,c[200005],lowb[200005],d[200005],qn;
vector<int> h[200005];
int tree[2800005];
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)^48);
}
void add(int x,int k){
    while(x<=n){
        tree[++lowb[x]]=k;
        x+=x&-x;
    }
} 
int qry(int x,int k){
    int ans=0,ls,rs,mid;
    while(x){
    	ls=lowb[x-1]+1,rs=lowb[x];
    	while(ls<rs){
    		mid=(ls+rs)>>1;
    		if(tree[mid]<k){
    			ans+=(mid-ls+1);
    			ls=mid+1;
			}
			else{
				rs=mid-1;
			}
		}
		if(ls==rs&&tree[ls]<k){
			ans++;
		}
        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];
        lowb[i+1]=lowb[i]+(i&-i);
    }
    sort(c+1,c+n+1);
    qn=n;
    for(int i=1;i<=n;i++){
		ls=1,rs=n;
    	while(ls<rs){
    		mid=(ls+rs)>>1;
    		if(c[mid]<a[i]){
    			ls=mid+1;
			}
			else{
				rs=mid;
			}
		}
		a[i]=ls;
        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;
}