这是代码;
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int pls[maxn*40],prs[maxn*40];
int sta[maxn*40],root[maxn],top,id;
long long cnt[maxn*40];
inline int newnode(){
return top?sta[top--]:++id;
}
inline void delnode(int p){
cnt[p]=0; sta[++top]=p; return;
}
inline void pushup(int p){
cnt[p]=cnt[pls[p]]+cnt[prs[p]];
return;
}
inline void update(int d,int &p,int pl,int pr,int k){
if(!p) p=newnode();
if(pl==pr){cnt[p]+=k;return;}
int mid=(pl+pr)>>1;
if(d<=mid) update(d,pls[p],pl,mid,k);
else update(d,prs[p],mid+1,pr,k);
return pushup(p);
}
inline void split(int l,int r,int &p,int &q,int pl,int pr){
if(!p or l>pr or r<pl) return;
if(l<=pl and pr<=r){q=p,p=0;return;}
if(!q) q=newnode();
int mid=(pl+pr)>>1;
if(l<=mid) split(l,r,pls[p],pls[q],pl,mid);
if(r>mid) split(l,r,prs[p],prs[q],mid+1,pr);
return pushup(q);
}
inline void merge(int &p,int &q,int pl,int pr){
if(!p) return;
if(!q){q=p,p=0;return;}
if(pl==pr){cnt[q]+=cnt[p];delnode(p);return;}
int mid=(pl+pr)>>1;
merge(pls[p],pls[q],pl,mid);
merge(prs[p],prs[q],mid+1,pr);
return pushup(q);
}
inline int querycnt(int l,int r,int p,int pl,int pr){
if(!p) return 0;
if(l<=pl and pr<=r) return cnt[p];
int mid=(pl+pr)>>1,ans=0;
if(l<=mid) ans+=querycnt(l,r,pls[p],pl,mid);
if(r>mid) ans+=querycnt(l,r,prs[p],mid+1,pr);
return ans;
}
inline int querykth(long long d,int p,int pl,int pr){
if(pl==pr) return pl;
int mid=(pl+pr)>>1;
if(cnt[pls[p]]>=d) return querykth(d,pls[p],pl,mid);
else return querykth(d-cnt[pls[p]],prs[p],mid+1,pr);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,m;cin>>n>>m;
int opt,id,v,now=1; long long u;
for(int i=1;i<=n;i++){
cin>>u; update(i,root[1],1,n,u);
}
for(int i=1;i<=m;i++){
cin>>opt>>id>>u;
if(opt^1 and opt^4) cin>>v;
if(opt==0) split(u,v,root[id],root[++now],1,n);
else if(opt==1) merge(root[id],root[u],1,n);
else if(opt==2) update(v,root[id],1,n,u);
else if(opt==3) cout<<querycnt(u,v,root[id],1,n)<<"\n";
else if(cnt[root[id]]<u) cout<<"-1\n";
else cout<<querykth(u,root[id],1,n)<<"\n";
}
return 0;
}