Description 给出序列 a1，a2，…，an（0≤ai≤109），有关序列的两种操作。
ai（1≤i≤n）变成 x（0≤x≤109）。求 al，al+1，…，ar（1≤l≤r≤n）第 k（1≤k≤r-l+1）小。题解 很显然，查询待修改的区间第k大一般的数据结构已经无法实现。这里给出树套树实现查询的数据结构。
线段树+权值线段树
对于每个线段树上的点维护一颗权值线段树树保存该区间所有数。容易发现对于每个修改操作复杂度是 O(nlog2n) ,而对于查询操作，先将在查询区间内的线段树中的点放入一个数组，由线段树性质得最多 logn 个，然后按照权值线段树求第k大的方法查询，时间复杂度 O(nlog2n) .
注意：线段树开点应开n*4个而不是n*2个。Code: #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> using namespace std; const int Maxn=2e4+5; const int Maxn2=4e6+2e5+50+Maxn; inline int read() { char ch=getchar();int i=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){i=(i<<3)+(i<<1)+ch-'0';ch=getchar();} return i*f; } int n,m,a[Maxn],tr[Maxn*2],C,lc[Maxn2],rc[Maxn2],sze[Maxn2],cnt0,rk[Maxn*2]; struct node { int val,id,op; friend inline bool operator <(const node &a,const node &b) { return a.val<b.val; } }b[Maxn*2]; struct Q { int op,l,r,val; }q[Maxn]; inline void insert2(int now,int l,int r,int val) { if(l==r) { sze[now]++; return; } int mid=(l+r)>>1; if(val<=mid) { if(!lc[now])lc[now]=++C; insert2(lc[now],l,mid,val); } else { if(!rc[now])rc[now]=++C; insert2(rc[now],mid+1,r,val); } sze[now]=(lc[now]?sze[lc[now]]:0)+(rc[now]?sze[rc[now]]:0); } inline void insert(int k,int l,int r,int pos,int val) { if(!tr[k])tr[k]=++C; insert2(tr[k],1,Maxn*2,val); if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)insert(k<<1,l,mid,pos,val); else insert(k<<1|1,mid+1,r,pos,val); } inline void del2(int now,int l,int r,int val) { if(l==r) { sze[now]--; return; } int mid=(l+r)>>1; if(val<=mid) { if(!lc[now])lc[now]=++C; del2(lc[now],l,mid,val); } else { if(!rc[now])rc[now]=++C; del2(rc[now],mid+1,r,val); } sze[now]=(lc[now]?sze[lc[now]]:0)+(rc[now]?sze[rc[now]]:0); } inline void del(int k,int l,int r,int pos,int val) { if(!tr[k])tr[k]=++C; del2(tr[k],1,Maxn*2,val); if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)del(k<<1,l,mid,pos,val); else del(k<<1|1,mid+1,r,pos,val); } struct num { int l,r,id; num(){} num(int l,int r,int id):l(l),r(r),id(id){} }nums[50]; int C2; inline void getin(int k,int l,int r,int L,int R) { if(l>=L&&r<=R) { nums[++C2].id=tr[k]; nums[C2].l=1; nums[C2].r=Maxn*2; return; } int mid=(l+r)>>1; if(L<=mid)getin(k<<1,l,mid,L,R); if(R>mid)getin(k<<1|1,mid+1,r,L,R); } inline int calclc() { int res=0; for(int i=1;i<=C2;i++) { res+=sze[lc[nums[i].id]]; } return res; } inline void getinlc() { for(int i=1;i<=C2;i++) { nums[i].id=lc[nums[i].id]; nums[i].r=((nums[i].l+nums[i].r)>>1); } } inline void getinrc() { for(int i=1;i<=C2;i++) { nums[i].id=rc[nums[i].id]; nums[i].l=(((nums[i].l+nums[i].r)>>1)+1); } } inline int maxn(num x) { while(x.l!=x.r) { if(sze[rc[x.id]])x.id=rc[x.id],x.l=((x.l+x.r)>>1)+1; else x.id=lc[x.id],x.r=((x.l+x.r)>>1);; } return x.l; } inline int maxlc() { int res=0; for(int i=1;i<=C2;i++) { num x=nums[i]; num t; t.id=lc[x.id]; t.l=x.l; t.r=((x.l+x.r)>>1); res=max(res,maxn(t)); } return res; } inline bool judgerc() { for(int i=1;i<=C2;i++) { if(rc[nums[i].id])return 1; } return 0; } inline int maxnow() { int res=0; for(int i=1;i<=C2;i++) { res=max(res,maxn(num(nums[i].l,nums[i].r,nums[i].id))); } return res; } inline int query(int l,int r,int k) { memset(nums,0,sizeof(nums)); C2=0; getin(1,1,n,l,r); while(1) { int t=calclc(); if(t>k) { getinlc(); continue; } else if(t==k) { return maxlc(); } else if(judgerc()) { k=k-t; getinrc(); } else return maxnow(); } } inline void l_b() { int t=0; sort(b+1,b+cnt0+1); for(int i=1;i<=cnt0;i++) { if(i==1||b[i].val!=b[i-1].val)t++; rk[t]=b[i].val; if(b[i].op)a[b[i].id]=t; else q[b[i].id].val=t; } } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) { b[++cnt0].val=read(); b[cnt0].id=i; b[cnt0].op=1; } for(int i=1;i<=m;i++) { q[i].op=read(); if(q[i].op==0) { q[i].l=read(); q[i].val=read(); b[++cnt0].val=q[i].val; b[cnt0].op=0; b[cnt0].id=i; } else { q[i].l=read(); q[i].r=read(); q[i].val=read(); } } l_b(); for(int i=1;i<=n;i++) { insert(1,1,n,i,a[i]); } for(int i=1;i<=m;i++) { int _=q[i].op; if(_==0) { int d=q[i].l,x=q[i].val; del(1,1,n,d,a[d]); a[d]=x; insert(1,1,n,d,x); } else { int l=q[i].l,r=q[i].r,k=q[i].val; cout<<rk[query(l,r,k)]<<endl; } } }