来自FallDream的博客，未经允许，请勿转载。
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)
n,m<=50000 1s/128MB
这道题我是不知道怎么做 传统的动态区间k大都可以实现这些操作 但是
线段树套权值线段树：时间nlog^2n 空间nlog^2n 这道题空间卡成这样 理论上讲是不够的
线段树套平衡树 空间只有nlogn 但是时间nlog^3n 这居然能过？？？？
不管 数据水，所以上面两个都能过 比较好奇出题人写的啥优秀做法。
#include<iostream> #include<cstdio> #include<algorithm> #define MV 10000000 #define MN 50000 #define N 65536 using namespace std; 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 * 10 + ch - '0';ch = getchar();} return x * f; } struct ques{int op,l,r,x;}q[MN+5]; struct Tree{int l,r,x;}T[MV]; int n,m,rt[N*2+5],a[MN+5],tot,cnt=0,J=1,l[MN*2+5],R[MN+5],rtnum; void Add(int x,int lt,int rt,int v,int ad) { T[x].x+=ad; if(lt==rt) return; int mid=lt+rt>>1; if(v<=mid) Add(!T[x].l?T[x].l=++cnt:T[x].l,lt,mid,v,ad); else Add(!T[x].r?T[x].r=++cnt:T[x].r,mid+1,rt,v,ad); } void Modify(int x,int v,int ad){for(x+=N;x;x>>=1) Add(rt[x],1,J,v,ad);} void GetRt(int l,int r) { for(rtnum=0,l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) { if(~l&1) R[++rtnum]=rt[l+1]; if( r&1) R[++rtnum]=rt[r-1]; } } int GetRk(int v) { if(!v) return 1; int l=1,r=J,mid,ans=1; while(l<r) { mid=l+r>>1; if(v<=mid) { r=mid; for(int j=1;j<=rtnum;++j) R[j]=T[R[j]].l; } else { l=mid+1; for(int j=1;j<=rtnum;++j) ans+=T[T[R[j]].l].x,R[j]=T[R[j]].r; } } for(int j=1;j<=rtnum;++j) ans+=T[R[j]].x; return ans; } int GetNum(int rk) { int l=1,r=J,mid,sum; while(l<r) { mid=l+r>>1;sum=0; for(int i=1;i<=rtnum;++i) sum+=T[T[R[i]].l].x; if(sum<rk) { rk-=sum;l=mid+1; for(int i=1;i<=rtnum;++i) R[i]=T[R[i]].r; } else { r=mid; for(int i=1;i<=rtnum;++i) R[i]=T[R[i]].l; } } return l; } int main() { tot=n=read();m=read(); for(int i=1;i<=N<<1;++i) rt[i]=++cnt; for(int i=1;i<=n;++i) l[i]=a[i]=read(); for(int i=1;i<=m;++i) { q[i].op=read();q[i].l=read();q[i].r=read(); if(q[i].op!=3) q[i].x=read(); else l[++tot]=q[i].r; } sort(l+1,l+tot+1); for(int i=2;i<=tot;++i) if(l[i]!=l[i-1]) l[++J]=l[i]; for(int i=1;i<=n;++i) Modify(i,a[i]=lower_bound(l+1,l+J+1,a[i])-l,1); for(int i=1;i<=m;++i) { if(q[i].op==3) { Modify(q[i].l,a[q[i].l],-1); Modify(q[i].l,q[i].r=lower_bound(l+1,l+J+1,q[i].r)-l,1); a[q[i].l]=q[i].r; } else { GetRt(q[i].l,q[i].r); if(q[i].op==1) printf("%d ",GetRk(lower_bound(l+1,l+J+1,q[i].x)-l-1)); if(q[i].op==2) printf("%d ",l[GetNum(q[i].x)]); if(q[i].op==4) { int rk=GetRk(lower_bound(l+1,l+J+1,q[i].x)-l-1)-1; GetRt(q[i].l,q[i].r); printf("%d ",l[GetNum(rk)]); } if(q[i].op==5) { int rk=GetRk(upper_bound(l+1,l+J+1,q[i].x)-l-1); GetRt(q[i].l,q[i].r); printf("%d ",l[GetNum(rk)]); } } } return 0; }