rt，之前写的 vector 传参被卡死，学习正常写法之后样例都过不了。

主要 bug 是一个询问会多次被更新答案。

#include<bits/stdc++.h>
#define N 300005
#define ll long long
#define lb x&-x
using namespace std;
int n,m,len,len1,len2;
ll ans[N/6+5],bit[N];
struct query{
    int l,r,id;
    ll k;
}q[N+N/3],q1[N+N/3],q2[N+N/3];
void add(int x,ll k){
    for(;x<=n;x+=lb){
        bit[x]+=k;
    }
}
ll sum(int x){
    ll ret=0;
    for(;x;x-=lb){
        ret+=bit[x];
    }
    return ret;
}
void solve(int ql,int qr,ll l,ll r){
    if(ql>qr){
        return;
    }
    if(l==r){
        for(int i=ql;i<=qr;++i){
            if(q[i].l){
                ans[q[i].id]=l;
            }
        }
        return;
    }
    ll mid=(l+r)/2;
    len1=len2=0;
    for(int i=ql;i<=qr;++i){
        if(q[i].l){
            ll p=sum(q[i].r)-sum(q[i].l-1);
            if(p>=q[i].k){
                q1[++len1]=q[i];
            }else{
                q2[++len2]=q[i];
                q2[len2].k-=p;
            }
        }else{
            if(q[i].k<=mid){
                add(q[i].id,1);
                q1[++len1]=q[i];
            }else{
                q2[++len2]=q[i];
            }
        }
    }
    for(int i=1;i<=len1;++i){
        q[ql+i-1]=q1[i];
        if(!q1[i].l){
            add(q1[i].id,-1);
        }
    }
    for(int i=1;i<=len2;++i){
        q[ql+len1+i-1]=q2[i];
    }
    solve(ql,ql+len1-1,l,mid);
    solve(ql+len1,qr,mid+1,r);
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        ll x;
        cin>>x;
        q[++len]={0,0,i,x};
    }
    for(int i=1,l,r;i<=m;++i){
        ll k;
        cin>>l>>r>>k;
        q[++len]={l,r,i,k};
    }
    solve(1,len,0,1e14);
    for(int i=1;i<=m;++i){
        cout<<ans[i]<<'\n';
    }
}