区间第 $K$ 小，直接树套树
外层树状数组维护区间，内层权值线段树维护排名
和正常的权值线段树类似，查询第 $K$ 小时也是在线段树上二分，但是此时不是两颗线段树作差，而是树状数组上的 $2log_n$ 个线段树作差
跳的话就 $2log_n$ 个节点一起跳就好了
要记得离散化
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,M=2e7+7; int rt[N],t[M],L[M],R[M],cnt; int pos,v,res;//位置，加还是减，询问结果 inline void change(int &o,int l,int r)//修改权值线段树 { if(!o) o=++cnt; t[o]+=v; if(l==r) return; int mid=l+r>>1; pos<=mid ? change(L[o],l,mid) : change(R[o],mid+1,r); } int n,m,A[N],B[N],tot;//A为原序列，B是离散化后的序列(包括操作时加入的值) int tmpl[N],tmpr[N],tl,tr,K;//左右各logn个节点 void query(int l,int r) { if(l==r) { res=B[l]; return; } int sum=0,mid=l+r>>1; for(int i=1;i<=tl;i++) sum-=t[ L[tmpl[i]] ]; for(int i=1;i<=tr;i++) sum+=t[ L[tmpr[i]] ];//作差 if(K<=sum) { for(int i=1;i<=tl;i++) tmpl[i]=L[tmpl[i]]; for(int i=1;i<=tr;i++) tmpr[i]=L[tmpr[i]];//一起跳 query(l,mid); return; } for(int i=1;i<=tl;i++) tmpl[i]=R[tmpl[i]]; for(int i=1;i<=tr;i++) tmpr[i]=R[tmpr[i]]; K-=sum; query(mid+1,r); } inline void ADD(int x)//树状数组上修改 { pos=lower_bound(B+1,B+tot+1,A[x])-B;//先找到位置 for(int i=x;i<=n;i+=i&-i) change(rt[i],1,tot); } inline void QUERY(int l,int r)//处理询问 { tl=tr=0; for(int i=l-1;i;i-=i&-i) tmpl[++tl]=rt[i];// for(int i=r;i;i-=i&-i) tmpr[++tr]=rt[i];// res=0; query(1,tot); printf("%d ",res); } int dl[N],dr[N],dk[N],dp[N],dt[N];//读入的数据 int main() { n=read(),m=read(); char s[7]; for(int i=1;i<=n;i++) A[i]=read(),B[++tot]=A[i]; for(int i=1;i<=m;i++) { scanf("%s",s); if(s[0]=='Q') dl[i]=read(),dr[i]=read(),dk[i]=read(); else dp[i]=read(),dt[i]=read(),B[++tot]=dt[i];//询问的也要一起离散化 } sort(B+1,B+tot+1); tot=unique(B+1,B+tot+1)-B-1; v=1; for(int i=1;i<=n;i++) ADD(i); for(int i=1;i<=m;i++) { if(dk[i]) { K=dk[i],QUERY(dl[i],dr[i]); continue; } v=-1; ADD(dp[i]); A[dp[i]]=dt[i];//A也要改变 v=1; ADD(dp[i]); } return 0; }