1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)
额，这个题，看了一眼就知道是线段树套线段树啦，所以随手糊一发
#pragma GCC opitmize("O3")
#pragma G++ opitmize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 50010
#define gR 0,10000000,c[x].rt
using namespace std;
int t=0,n,m,v[50010];
struct dn{ int l,r,s; dn(){l=r=s=0;} } s[11000010];
struct Segment{
int rt; Segment(){ rt=0; }
void insert(int l,int r,int& x,int k){
if(!x) x=++t;
if(l==r){ ++s[x].s; return; }
int m=l+r>>1;++s[x].s;
if(k<=m) insert(l,m,s[x].l,k);
else insert(m+1,r,s[x].r,k);
}
void remove(int l,int r,int& x,int k){
if(l==r){ --s[x].s; return; }
int m=l+r>>1; --s[x].s;
if(k<=m) remove(l,m,s[x].l,k);
else remove(m+1,r,s[x].r,k);
}
int gMax(int l,int r,int x){
if(l==r) return l;
int m=l+r>>1;
if(s[s[x].r].s) return gMax(m+1,r,s[x].r);
else return gMax(l,m,s[x].l);
}
int gMin(int l,int r,int x){
if(l==r) return l;
int m=l+r>>1;
if(s[s[x].l].s) return gMin(l,m,s[x].l);
else return gMin(m+1,r,s[x].r);
}
int gRank(int l,int r,int x,int k){
if(l==r) return 0;
int m=l+r>>1;
if(k<=m) return gRank(l,m,s[x].l,k);
else return s[s[x].l].s+gRank(m+1,r,s[x].r,k);
}
int gPre(int l,int r,int x,int k){
if(l==r) return k;
int m=l+r>>1;
if(k<=m) return gPre(l,m,s[x].l,k);
else {
int p=gPre(m+1,r,s[x].r,k);
if(p==k && s[s[x].l].s) return gMax(l,m,s[x].l);
else return p;
}
}
int gSuc(int l,int r,int x,int k){
if(l==r) return k;
int m=l+r>>1;
if(m<k) return gSuc(m+1,r,s[x].r,k);
else {
int p=gSuc(l,m,s[x].l,k);
if(p==k && s[s[x].r].s) return gMin(m+1,r,s[x].r);
else return p;
}
}
} c[200010];
void modify(int l,int r,int x,int p,int k){
c[x].remove(gR,v[p]); c[x].insert(gR,k);
if(l==r) return;
int m=l+r>>1;
if(p<=m) modify(l,m,x<<1,p,k);
else modify(m+1,r,x<<1|1,p,k);
}
int getrank(int l,int r,int x,int L,int R,int k){
if(L<=l && r<=R) return c[x].gRank(gR,k);
int m=l+r>>1,S=0;
if(L<=m) S+=getrank(l,m,x<<1,L,R,k);
if(m<R) S+=getrank(m+1,r,x<<1|1,L,R,k);
return S;
}
int getpre(int l,int r,int x,int L,int R,int k){
if(L<=l && r<=R){
int p=c[x].gPre(gR,k);
return p==k?-1<<30:p;
}
int m=l+r>>1,S=-1<<30;
if(L<=m) S=max(S,getpre(l,m,x<<1,L,R,k));
if(m<R) S=max(S,getpre(m+1,r,x<<1|1,L,R,k));
return S;
}
int getsuc(int l,int r,int x,int L,int R,int k){
if(L<=l && r<=R){
int p=c[x].gSuc(gR,k);
return p==k?1<<30:p;
}
int m=l+r>>1,S=1<<30;
if(L<=m) S=min(S,getsuc(l,m,x<<1,L,R,k));
if(m<R) S=min(S,getsuc(m+1,r,x<<1|1,L,R,k));
return S;
}
int gKth(int l,int r,int k){
int L=0,R=1e8;
for(int m;L<R;){
m=L+R+1>>1;
if(getrank(1,n,1,l,r,m)+1<=k) L=m;
else R=m-1;
}
return L;
}
void build(int l,int r,int x){
for(int i=l;i<=r;++i) c[x].insert(gR,v[i]);
if(l==r) return;
int m=l+r>>1;
build(l,m,x<<1);
build(m+1,r,x<<1|1);
}
int main(){
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",v+i);
build(1,n,1);
for(int o,a,b,c;m--;){
scanf("%d%d%d",&o,&a,&b);
if(o^3) scanf("%d",&c);
if(o==1) printf("%d
",getrank(1,n,1,a,b,c)+1);
else if(o==2) printf("%d
",gKth(a,b,c));
else if(o==3) modify(1,n,1,a,b),v[a]=b;
else if(o==4) printf("%d
",getpre(1,n,1,a,b,c));
else if(o==5) printf("%d
",getsuc(1,n,1,a,b,c));
}
}正解是线段树套（treap，splay，替罪羊。。。）