线段树套fhq-treap
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rint register int
#define il inline
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T> inline void read(T &x){
x=0; char c=getchar(); int f=1;
while(!isdigit(c)) {if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
const int N=50010,M=N<<2;
const int INF=2147483647;
int n,m,tot;
struct Node{
int s[2],v,key,size;
void init(int _v){
v=_v; key=rand();
size=1;
}
}fhq[1300010];
struct Sgt{
int l,r,root;
void init(int _l,int _r){l=_l;r=_r;}
}tr[M];
int w[N];
il int New(int v){ fhq[++tot].init(v);return tot; }
il void Pushup(int x){ fhq[x].size=fhq[fhq[x].s[0]].size+fhq[fhq[x].s[1]].size+1; }
il void Split(int u,int k,int &x,int &y){
if(!u){x=y=0; return;}
if(fhq[u].v<=k) x=u,Split(fhq[u].s[1],k,fhq[u].s[1],y);
else y=u,Split(fhq[u].s[0],k,x,fhq[u].s[0]);
Pushup(u);
}
il int Merge(int x,int y){
if(!x||!y) return x+y;
if(fhq[x].key>fhq[y].key) {
fhq[x].s[1]=Merge(fhq[x].s[1],y);
Pushup(x); return x;
} else{
fhq[y].s[0]=Merge(x,fhq[y].s[0]);
Pushup(y); return y;
}
}
il void Insert(int p,int v){
int A,B;
Split(tr[p].root,v,A,B);
tr[p].root=Merge(Merge(A,New(v)),B);
}
il void Delete(int p,int v){
int A,B,C;
Split(tr[p].root,v,A,C);
Split(A,v-1,A,B); B=Merge(fhq[B].s[0],fhq[B].s[1]);
tr[p].root=Merge(Merge(A,B),C);
}
#define ls (p<<1)
#define rs (p<<1|1)
il void Build(int p,int l,int r){
tr[p].init(l,r);
Insert(p,-INF); Insert(p,INF);
for(rint i=l;i<=r;i++) Insert(p,w[i]);
if(l==r) return;
int mid=l+r>>1;
Build(ls,l,mid),Build(rs,mid+1,r);
}
il void Modify(int p,int pos,int v){
Delete(p,w[pos]);
Insert(p,v);
if(tr[p].l==tr[p].r&&tr[p].l==pos){ w[pos]=v; return; }
int mid=tr[p].l+tr[p].r>>1;
if(pos<=mid) Modify(ls,pos,v);
else Modify(rs,pos,v);
}
il int Getrk(int p,int l,int r,int v){
if(l<=tr[p].l&&tr[p].r<=r) {
int A,B;
Split(tr[p].root,v,A,B);
int ret=fhq[A].size-1;
tr[p].root=Merge(A,B);
return ret;
}
int mid=tr[p].l+tr[p].r>>1,sum=0;
if(l<=mid) sum+=Getrk(ls,l,r,v);
if(r>mid) sum+=Getrk(rs,l,r,v);
return sum;
}
il int Getpre(int p,int l,int r,int x){
if(l<=tr[p].l&&tr[p].r<=r){
int A,B;
Split(tr[p].root,x-1,A,B);
int u=A; while(fhq[u].s[1]) u=fhq[u].s[1];
tr[p].root=Merge(A,B);
return fhq[u].v;
}
int mid=tr[p].l+tr[p].r>>1,ret=-INF;
if(l<=mid) ret=std::max(ret,Getpre(ls,l,r,x));
if(r>mid) ret=std::max(ret,Getpre(rs,l,r,x));
return ret;
}
il int Getnxt(int p,int l,int r,int x){
if(l<=tr[p].l&&tr[p].r<=r){
int A,B;
Split(tr[p].root,x,A,B);
int u=B; while(fhq[u].s[0]) u=fhq[u].s[0];
tr[p].root=Merge(A,B);
return fhq[u].v;
}
int mid=tr[p].l+tr[p].r>>1,ret=INF;
if(l<=mid) ret=std::min(ret,Getnxt(ls,l,r,x));
if(r>mid) ret=std::min(ret,Getnxt(rs,l,r,x));
return ret;
}
#undef ls
#undef rs
int main(){
read(n);read(m);
for(int i=1;i<=n;i++) read(w[i]);
Build(1,1,n);
while(m--){
int opt; read(opt);
if(opt==1) {
int l,r,x; read(l),read(r),read(x);
printf("%d\n",Getrk(1,l,r,x-1)+1);
} if(opt==2){
int l,r,k; read(l),read(r),read(k);
int L=0,R=1e8;
while(L<R){
int mid=L+R+1>>1;
if(Getrk(1,l,r,mid-1)+1<=k) L=mid;
else R=mid-1;
} printf("%d\n",L);
} if(opt==3){
int pos,x; read(pos),read(x);
Modify(1,pos,x);
} if(opt==4){
int l,r,x; read(l),read(r),read(x);
printf("%d\n",Getpre(1,l,r,x));
} if(opt==5){
int l,r,x; read(l),read(r),read(x);
printf("%d\n",Getnxt(1,l,r,x));
}
}
return 0;
}