挂在了1,3,4,5点上qwq

#include<iostream>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<cstring>
using namespace std;
namespace ds {
#define p1 first
#define p2 second
    const int N=50010,LG=100;
    int cnt;
    int val[N*LG],siz[N*LG],wei[N*LG],ls[N*LG],rs[N*LG];
    inline int New(int v){
        val[++cnt]=v;
        siz[cnt]=1;
        wei[cnt]=(int)random();
        ls[cnt]=rs[cnt]=0;
        return cnt;
    }
    struct treap{
        int rt;
        inline void push_up(int nd){siz[nd]=1+siz[ls[nd]]+siz[rs[nd]];}
        pair<int,int>split(int nd,int k){
            if(!nd)return {0,0};
            if(val[nd]<=k){
                pair<int,int>o=split(rs[nd],k);
                rs[nd]=o.p1;push_up(nd);
                return{nd,o.p2};
            }
            else{
                pair<int,int>o=split(ls[nd],k);
                ls[nd]=o.p2;push_up(nd);
                return{o.p1,nd};
            }
        }
        int merge(int u,int v){
            if(!u||!v)return u|v;
            if(wei[u]<wei[v]){
                rs[u]=merge(rs[u],v);
                push_up(u);
                return u;
            }
            else{
                ls[v]=merge(u,ls[v]);
                push_up(v);
                return v;
            }
        }
        inline void insert(int k){
            pair<int,int>o=split(rt,k);
            rt=merge(o.p1,merge(New(k),o.p2));
        }
        inline void erase(int k){
            pair<int,int>o=split(rt,k);
            pair<int,int>p=split(o.p1,k-1);
            rt=merge(p.p1,o.p2);
        }
        inline int get_siz(int l,int r){
            pair<int,int>o=split(rt,r);
            pair<int,int>p=split(o.p1,l-1);
            int res=siz[p.p2];
            rt=merge(merge(p.p1,p.p2),o.p2);
            return res;
        }
    };
}
const int N=50010,inf=2147483647;
inline int read(){
    int i=getchar(),r=0;
    while(i<'0'||i>'9')i=getchar();
    while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar();
    return r;
}
ds::treap val[N<<2];
int L[N<<2],R[N<<2],ls[N<<2],rs[N<<2],cnt,rt;
inline int New(int L_,int R_,int ls_,int rs_){
    L[++cnt]=L_,R[cnt]=R_,ls[cnt]=ls_,rs[cnt]=rs_;val[cnt].rt=0;
    return cnt;
}
int build(int l,int r){
    if(l==r)return New(l,r,0,0);
    int mid=(l+r)>>1;
    return New(l,r,build(l,mid),build(mid+1,r));
}
void add(int nd,int pos,int k){
    val[nd].insert(k);
    if(L[nd]==R[nd])return;
//    cout<<R[ls[nd]]<<' ';
    if(pos<=R[ls[nd]])add(ls[nd],pos,k);
    else add(rs[nd],pos,k);
}
void del(int nd,int pos,int k){
    val[nd].erase(k);
    if(L[nd]==R[nd])return;
    if(pos<=R[ls[nd]])del(ls[nd],pos,k);
    else del(rs[nd],pos,k);
}
int n,m,a[N],b[N<<1],u;
struct offline{int typ,x,y,z;}ask[N];
void get_q(){
    cin>>n>>m;
    map<int,int>mp;
    memset(b,0xff,sizeof(b));
    for(int i=1;i<=n;i++)a[i]=b[++u]=read();
    for(int i=1;i<=m;i++){
        int typ=read(),x=read(),y=read();
        if(typ==1)b[++u]=read(),ask[i]={typ,x,y,b[u]};
        else if(typ==2)ask[i]={typ,x,y,read()};
        else if(typ==3)b[++u]=y,ask[i]={typ,x,y};
        else b[++u]=read(),ask[i]={typ,x,y,b[u]};
    }
    sort(b+1,b+u+1);u=0;
    for(int i=1;b[i]>=b[i-1];i++)if(b[i]!=b[u])b[++u]=b[i],mp[b[i]]=u;
    for(int i=1;i<=n;i++)a[i]=mp[a[i]];
    for(int i=1;i<=m;i++)
        if(ask[i].typ==1||ask[i].typ==4||ask[i].typ==5)ask[i].z=mp[ask[i].z];
        else if(ask[i].typ==3)ask[i].y=mp[ask[i].y];
//    for(int i=1;i<=n;i++)cout<<a[i]<<' ';cout<<endl;
//    for(int i=1;i<=m;i++)cout<<ask[i].typ<<' '<<ask[i].x<<' '<<ask[i].y<<' '<<ask[i].z<<endl;
}
int get_rank(int nd,int l,int r,int k){
    if(L[nd]==R[nd])return 1;
    if(k<=R[ls[nd]])return get_rank(ls[nd],l,r,k);
    else return val[ls[nd]].get_siz(l,r)+get_rank(rs[nd],l,r,k);
}
inline int kth(int l,int r,int k){
    int nd=rt;
    while(L[nd]!=R[nd]){
        int t=val[ls[nd]].get_siz(l,r);
        if(k<=t)nd=ls[nd];
        else k-=t,nd=rs[nd];
    }
    return b[L[nd]];
}
inline void reset(int pos,int k){
    del(rt,a[pos],pos);
    a[pos]=k;
    add(rt,a[pos],pos);
}
inline int get_front(int l,int r,int k){
    int rk=get_rank(rt,l,r,k);
    if(rk==1)return -inf;
    else return kth(l,r,rk-1);
}
int get_back(int l,int r,int k){
    int rk=get_rank(rt,l,r,k);
    if(rk==r-l+2)return inf;
    else return kth(l,r,rk);
}
void init(){
    get_q();
    rt=build(1,u);
    for(int i=1;i<=n;i++)add(rt,a[i],i);
}
int main(){
//    freopen("read.in","r",stdin);
    init();
    for(int i=1;i<=m;i++){
        if(ask[i].typ==1)printf("%d\n",get_rank(rt,ask[i].x,ask[i].y,ask[i].z));
        else if(ask[i].typ==2)printf("%d\n",kth(ask[i].x,ask[i].y,ask[i].z));
        else if(ask[i].typ==3)reset(ask[i].x,ask[i].y);
        else if(ask[i].typ==4)printf("%d\n",get_front(ask[i].x,ask[i].y,ask[i].z));
        else printf("%d\n",get_back(ask[i].x,ask[i].y,ask[i].z));
    }
    return 0;
}