分析

一共 5 个操作：

• 操作 1：
  查询 $v$ 在 $[l, r]$ 中的排名
  那么我们将线段树相应的区间比 $x$ 小的数的个数 $cnt$ 统计一下， $ans = \sum{cnt} + 1$

• 操作 2：
  查询 $[l, r]$ 排名为 $k$ 的值，可以做个二分，转化为操作 1

• 操作 3：
  将 $pos$ 的值改为 $v$，相当于 Splay 中的 删除+插入 操作，然后对应地在线段树相应的区间修改即可。

• 操作 4, 5：
  查询前缀后缀，见代码。

难点还是在于细节 $qwq$

#include<bits/stdc++.h>
using namespace std;

inline void read(int &x) {
    int s=0;x=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=15e5+5, INF=2147483647;

int n, q, w[N];

// 伸展树 data ------------------------------------------
struct node{
    int s[2], p, v;
    int size;

    void init(int _p, int _v){
        p=_p, v=_v;
        size=1;
    }
}tr[N];
int idx;

// 开始伸展树操作 ----------------------------------------
void pushup(int u){
    tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1;
}

void rotate(int x){
    int y=tr[x].p, z=tr[y].p;
    int k= tr[y].s[1]==x;
    tr[z].s[tr[z].s[1]==y]=x, tr[x].p=z;
    tr[tr[x].s[k^1]].p=y, tr[y].s[k]=tr[x].s[k^1];
    tr[y].p=x, tr[x].s[k^1]=y;
    pushup(y), pushup(x);
}

void splay(int &root, int x, int k){
    while(tr[x].p!=k){
        int y=tr[x].p, z=tr[y].p;
        if(z!=k)
            if((tr[z].s[1]==y) ^ (tr[y].s[1]==x)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(k==0) root=x;
}

void insert(int &root, int v){
    int u=root, p=0;
    while(u) p=u, u=tr[u].s[v>tr[u].v];
    u=++idx;
    if(p) tr[p].s[v>tr[p].v]=u;
    tr[u].init(p, v);
    splay(root, u, 0);
}

int get_k(int root, int v){
    int u=root, k=0;
    while(u){
        if(v>tr[u].v) k+=tr[tr[u].s[0]].size+1, u=tr[u].s[1];
        else u=tr[u].s[0];
    }
    return k;
}

void remove(int &root, int v){
    int u=root;
    while(u && tr[u].v!=v) u=tr[u].s[v>tr[u].v];
    splay(root, u, 0);

    int pu=tr[u].s[0], su=tr[u].s[1];
    while(tr[pu].s[1]) pu=tr[pu].s[1];
    while(tr[su].s[0]) su=tr[su].s[0];
    splay(root, pu, 0), splay(root, su, pu);
    tr[su].s[0]=0;
}

void update(int &root, int p, int q){
    remove(root, p), insert(root, q); 
}

int get_pre(int root, int v){
    int u=root, res=-INF;
    while(u){
        if(tr[u].v<v) res=max(res, tr[u].v), u=tr[u].s[1];
        else u=tr[u].s[0];
    }
    return res;
}

int get_suf(int root, int v){
    int u=root, res=INF;
    while(u){
        if(v<tr[u].v) res=min(res, tr[u].v), u=tr[u].s[0];
        else u=tr[u].s[1]; 
    }
    return res;
}

// 线段树 data ------------------------------------------
int L[N], R[N], T[N];

// 开始线段树操作 ----------------------------------------
int ls(int u){return u<<1;}
int rs(int u){return u<<1|1;}

void build(int u, int l, int r){
    // 伸展树建树
    insert(T[u], -INF), insert(T[u], INF);
    for(int i=l; i<=r; i++) insert(T[u], w[i]);

    // 线段树建树
    L[u]=l, R[u]=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(ls(u), l, mid), build(rs(u), mid+1, r);   
}

int query_less(int u, int l, int r, int v){
    if(l<=L[u] && R[u]<=r) return get_k(T[u], v)-1;

    int mid=L[u]+R[u]>>1, res=0;
    if(l<=mid) res+=query_less(ls(u), l, r, v);
    if(r>mid) res+=query_less(rs(u), l, r, v);
    return res;
}

void change(int u, int p, int v){
    update(T[u], w[p], v);
    if(L[u]==R[u]) return;
    int mid=L[u]+R[u]>>1;
    if(p<=mid) change(ls(u), p, v);
    else change(rs(u), p, v);
}

int query_pre(int u, int l, int r, int v){
    if(l<=L[u] && R[u]<=r) return get_pre(T[u], v);
    int mid=L[u]+R[u]>>1, res=-INF;
    if(l<=mid) res=max(res, query_pre(ls(u), l, r, v));
    if(r>mid) res=max(res, query_pre(rs(u), l, r, v));
    return res;
}

int query_suf(int u, int l, int r, int v){
    if(l<=L[u] && R[u]<=r) return get_suf(T[u], v);
    int mid=L[u]+R[u]>>1, res=INF;

    if(l<=mid) res=min(res, query_suf(ls(u), l, r, v));
    if(r>mid) res=min(res, query_suf(rs(u), l, r, v));
    return res;
}

int main(){
    read(n), read(q);
    for(int i=1; i<=n; i++) read(w[i]);

    build(1, 1, n);

    while(q--){
        int op; read(op);
        if(op==1){
            int l, r, v; read(l), read(r), read(v);
            cout<<query_less(1, l, r, v)+1<<endl;
        }else if(op==2){
            int l, r, k; read(l), read(r), read(k);
            int ok=0, ng=1e8;
            while(ok<ng){
                int mid=ok+ng+1>>1;
                if(query_less(1, l, r, mid)+1<=k) ok=mid;
                else ng=mid-1;
            }
            cout<<ok<<endl;
        }else if(op==3){
            int p, v; read(p), read(v);
            change(1, p, v);
            w[p]=v;
        }else if(op==4){
            int l, r, v; read(l), read(r), read(v);
            cout<<query_pre(1, l, r, v)<<endl;
        }else if(op==5){
            int l, r, v; read(l), read(r), read(v);
            cout<<query_suf(1, l, r, v)<<endl;
        }
    }

    return 0;
}