P3834可持久化线段树2样例过不了求调

#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define INF 10000005
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-6;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
    bool f=0;int x=0;char ch;
    ch=gt();
    while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
    while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
    if(f)return -x;
    else return x;
}
template<class T>
inline void print(T x){
    char s[114];
    int top=0;
    if(x<0)pt('-');
    do{
        top++;
        if(x>=0)s[top]=(x%10)+48;
        else s[top]=(-(x%10)+48);
        x/=10;
    }while(x);
    while(top){pt(s[top]);top--;}
    pt('\n');
}
const int MAXN=1e6+10;
struct SegmentTree{
    long long val;
    int ls,rs;
    #define ls(x) tree[x].ls
    #define rs(x) tree[x].rs
    #define val(x) tree[x].val
}tree[30*MAXN];
int a[MAXN],b[MAXN];
int roots[MAXN];//roots记录每个历史版本的根节点
int tot=1;
void pushup(int p){val(p)=val(ls(p))+val(rs(p));}//维护和
void build(int p,int l,int r){//最初版本的树
    val(p)=0;
    if(l!=r){
        ls(p)=++tot;
        rs(p)=++tot;
        int mid=(l+r)>>1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        pushup(p);
    }
}
void update(int now,int nxt,int x,int L,int R,int c){//单点修改，now表示现在版本的节点，nxt表示新版本的节点
    if(L==R){
        val(nxt)+=c;
        return;
    }
    ls(nxt)=ls(now),rs(nxt)=rs(now);
    int mid=(L+R)>>1;
    if(x<=mid)ls(nxt)=++tot,update(ls(now),ls(nxt),x,L,mid,c);
    else rs(nxt)=++tot,update(rs(now),rs(nxt),x,mid+1,R,c);
    pushup(nxt);
}
int kth(int now,int lst,int k,int L,int R){
    if(L==R)return b[L];
    int mid=(L+R)>>1;
    if(val(ls(now))-val(ls(lst))>=k)return kth(ls(now),ls(lst),k,L,mid);
    else return kth(rs(now),rs(lst),k-val(ls(now))+val(ls(lst)),mid+1,R);
}
signed main(){
    int n=read(),q=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int m=unique(b+1,b+1+n)-b-1;
    build(1,1,m);
    roots[0]=1;
    for(int i=1;i<=n;i++){
        int l=lower_bound(b+1,b+1+m,a[i])-b;
        roots[i+1]=++tot;
        update(roots[i+1],roots[i],l,1,m,1);
    }
    while(q--){
        int l=read(),r=read(),k=read();
        cout<<kth(roots[r],roots[l-1],k,1,m)<<'\n';
    }
    return 0;
}