整体二分

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=2e5+5;

int n,m,cnt;
int ans[N],tree[N];
int maxn=INT_MIN,minn=INT_MAX;

struct node{
    int x,y,k,id,op;
}q[N<<1],q1[N<<1],q2[N<<1];

struct BIT{
    int p[N];
    void add(int x,int k){
        for(int i=x;i<=n;i+=lowbit(i)) p[i]+=k;
    }
    int sum(int x){
        int res=0;
        for(int i=x;i>=1;i-=lowbit(i)) res+=p[i];
        return res;
    }
}bit;

void solve(int l,int r,int vl,int vr){
    if(l>r) return;
    if(vl==vr){
        for(int i=l;i<=r;i++)
            if(q[i].op) ans[q[i].id]=vl;
        return;
    }
    int mid=vl+vr>>1;
    int cnt1=0,cnt2=0;
    for(int i=l;i<=r;i++){
        if(!q[i].op){
            if(q[i].x<=mid){
                bit.add(q[i].id,1);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
        else{
            int s=bit.sum(q[i].y)-bit.sum(q[i].x-1);
            if(s>=q[i].k) q1[++cnt1]=q[i];
            else{
                q[i].k-=s;
                q2[++cnt2]=q[i];
            }
        }
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].op) bit.add(q1[i].id,-1);
    for(int i=1;i<=cnt1;i++) q[i+l-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[i+l+cnt1-1]=q2[i];
    solve(l,l+cnt1-1,vl,mid);
    solve(l+cnt1,r,mid+1,vr);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        q[++cnt]={x,0,0,i,0};
        minn=min(minn,x),maxn=max(maxn,x);
    }
    for(int i=1;i<=m;i++){
        int x,y,k;
        cin>>x>>y>>k;
        q[++cnt]={x,y,k,i,1};
    }
    solve(1,cnt,minn,maxn);
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=2e5+5;

int n,m,cnt;
int ans[N],tree[N];
int maxn=INT_MIN,minn=INT_MAX;

struct node{
    int x,y,k,id,op;
}q[N<<1],q1[N<<1],q2[N<<1];

struct BIT{
    int p[N];
    void add(int x,int k){
        for(int i=x;i<=n;i+=lowbit(i)) p[i]+=k;
    }
    int sum(int x){
        int res=0;
        for(int i=x;i>=1;i-=lowbit(i)) res+=p[i];
        return res;
    }
}bit;

void solve(int l,int r,int vl,int vr){
    if(l>r) return;
    if(vl==vr){
        for(int i=l;i<=r;i++)
            if(q[i].op) ans[q[i].id]=vl;
        return;
    }
    int mid=vl+vr>>1;
    int cnt1=0,cnt2=0;
    for(int i=l;i<=r;i++){
        if(!q[i].op){
            if(q[i].x<=mid){
                bit.add(q[i].id,1);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
        else{
            int s=bit.sum(q[i].y)-bit.sum(q[i].x-1);
            if(s>=q[i].k) q1[++cnt1]=q[i];
            else{
                q[i].k-=s;
                q2[++cnt2]=q[i];
            }
        }
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].op) bit.add(q1[i].id,-1);
    for(int i=1;i<=cnt1;i++) q[i+l-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[i+l+cnt1-1]=q2[i];
    solve(l,l+cnt1-1,vl,mid);
    solve(l+cnt1,r,mid+1,vr);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        q[++cnt]={x,0,0,i,0};
        minn=min(minn,x),maxn=max(maxn,x);
    }
    for(int i=1;i<=m;i++){
        int x,y,k;
        cin>>x>>y>>k;
        q[++cnt]={x,y,k,i,1};
    }
    solve(1,cnt,minn,maxn);
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}