思路

若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

树套树
区间操作可以用我们熟悉的线段树
线段树上每个点 维护对应区间[l,r]的一颗平衡树
线段树深度logn,每层要维护n个节点,所以treap的内存是nlogn

操作2的话,二分顺便用操作1check就好
二分的答案一定是在序列中的 ,复杂度\(log^{3}n\)(真的2b啊,什么复杂度)
其他具体操作就不啰嗦了(复杂度普遍\(log^{2}n\))
而n=5e4的时候\(log^{2}n\)\(\sqrt{n}\)基本是相等的(分界线)

注意

线段树套平衡树
平衡树的种类也要选好
fhq-treap这种常数就比较大
普通treap就不错
splay也阔以

fhq-treap代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=5e4+7;
const int inf=0x7fffffff;
inline int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int w[maxn];
int ch[maxn*40][2],val[maxn*40],pri[maxn*40],siz[maxn*40],cnt;
namespace fhq_treap {
    void pushup(int x) {
        siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
    }
    int new_node(int x) {
        val[++cnt]=x;
        pri[cnt]=rand();
        siz[cnt]=1;
        return cnt;
    }
    int merge(int x,int y) {
        if(!x||!y) return x+y;
        if(pri[x]<pri[y]) {
            ch[x][1]=merge(ch[x][1],y);
            pushup(x);return x;
        } else {
            ch[y][0]=merge(x,ch[y][0]);
            pushup(y);return y;
        }                       
    }
    void split(int now,int k,int &x,int &y) {
        if(!now) x=y=0;
        else {
            if(val[now]<=k)
                x=now,split(ch[now][1],k,ch[x][1],y);
            else
                y=now,split(ch[now][0],k,x,ch[y][0]);
            pushup(now);
        }
    }
    int find(int &rt,int a) {
        int x,y;
        split(rt,a-1,x,y);
        int tmp=siz[x];
        rt=merge(x,y); 
        return tmp;
    }
    int k_th(int now,int k) {
        if(siz[now]<k||siz[now]==0||k==0) return 0x7fffffff;
        while(233) {
            if(siz[ch[now][0]]+1==k) return val[now];
            if(siz[ch[now][0]]>=k) now=ch[now][0];
            else k-=siz[ch[now][0]]+1,now=ch[now][1];
        }
    }
    void insert(int &rt,int a) {
        int x,y;
        split(rt,a,x,y);
        rt=merge(merge(x,new_node(a)),y);
    }
    void delet(int &rt,int a) {
        int x,y,z;
        split(rt,a,x,z);
        split(x,a-1,x,y);
        y=merge(ch[y][0],ch[y][1]);
        rt=merge(merge(x,y),z);
    }
    int qq(int &rt,int a) {
        int x,y,tmp;
        split(rt,a-1,x,y);
        tmp=k_th(x,siz[x]);
        rt=merge(x,y);
        return tmp==inf ? -inf : tmp;
    }
    int hj(int &rt,int a) {
        int x,y,tmp;
        split(rt,a,x,y);
        tmp=k_th(y,1);
        rt=merge(x,y);
        return tmp;
    }
}
struct node {
    int l,r,rt;
}e[maxn<<2];
void build(int l,int r,int rt) {
    e[rt].l=l,e[rt].r=r;
    FOR(i,l,r) fhq_treap::insert(e[rt].rt,w[i]);
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
void modify(int L,int k,int rt) {
    fhq_treap::delet(e[rt].rt,w[L]);
    fhq_treap::insert(e[rt].rt,k);
    if(e[rt].l==e[rt].r) return;
    int mid=(e[rt].l+e[rt].r)>>1;
    if(L<=mid) modify(L,k,rt<<1);
    else modify(L,k,rt<<1|1);
}
int find(int L,int R,int k,int rt) {
    if(L<=e[rt].l&&e[rt].r<=R)
        return fhq_treap::find(e[rt].rt,k);
    int mid=(e[rt].l+e[rt].r)>>1,ans=0;
    if(L<=mid) ans+=find(L,R,k,rt<<1);
    if(R>mid)  ans+=find(L,R,k,rt<<1|1);
    return ans;
}
int qq(int L,int R,int a,int rt) {
    if(L<=e[rt].l&&e[rt].r<=R) {
        return fhq_treap::qq(e[rt].rt,a);
    }
    int mid=(e[rt].l+e[rt].r)>>1,ans=-inf;
    if(L<=mid) ans=max(ans,qq(L,R,a,rt<<1));
    if(R>mid) ans=max(ans,qq(L,R,a,rt<<1|1));
    return ans;
}
int hj(int L,int R,int a,int rt) {
    if(L<=e[rt].l&&e[rt].r<=R) {
        return fhq_treap::hj(e[rt].rt,a);
    }
    int mid=(e[rt].l+e[rt].r)>>1,ans=inf;
    if(L<=mid) ans=min(ans,hj(L,R,a,rt<<1));
    if(R>mid) ans=min(ans,hj(L,R,a,rt<<1|1));
    return ans;
}
int main() {
    srand(time(NULL));
    int n=read(),m=read();
    FOR(i,1,n) w[i]=read();
    build(1,n,1);
    FOR(i,1,m) {
        int opt=read();
        if(opt==1) {
            int l=read(),r=read(),k=read(); 
            cout<<find(l,r,k,1)+1<<"\n";
        } else
        if(opt==2) {
            int l=read(),r=read(),k=read();
            int L=0,R=1e8+5,ans=0;
            while(L<=R) {
                int mid=(L+R)>>1;
                if(find(l,r,mid,1)+1<=k) ans=mid,L=mid+1;
                else R=mid-1;
            }
            cout<<ans<<"\n";
        } else
        if(opt==3) {
            int pos=read(),k=read();
            modify(pos,k,1);
            w[pos]=k;
        } else
        if(opt==4) {
            int l=read(),r=read(),k=read();
            cout<<qq(l,r,k,1)<<"\n"; 
        } else
        if(opt==5) {
            int l=read(),r=read(),k=read();
            cout<<hj(l,r,k,1)<<"\n";
        }
    }
    return 0;
}