```cpp
int L,R,x,k,ans,pos;
il int _max(re int x,re int y) {return x>y?x:y;}
il int _min(re int x,re int y) {return x<y?x:y;}
vd Build(int l,int r,int id) {
tr[id].root=0,tr[id].Insert(INF),tr[id].Insert(-INF);
FOR(i,l,r) tr[id].Insert(a[i]);
if(l==r) return;
int mid(l+((r-l)>>1));
Build(l,mid,id<<1),Build(mid+1,r,id<<1|1);
}
vd up(int l,int r,int id) {
tr[id].Del(a[pos]),tr[id].Insert(x);
if(l==r) return;
int mid(l+((r-l)>>1));
if(pos<=mid) up(l,mid,id<<1);
else up(mid+1,r,id<<1|1);
}
vd find(int l,int r,int id) {
if(L<=l&&r<=R) {
tr[id].Insert(x),ans+=tr[id].find(x)-1,tr[id].Del(x);
return;
} int mid(l+((r-l)>>1));
if(L<=mid) find(l,mid,id<<1);
if(mid<R) find(mid+1,r,id<<1|1);
}
vd find2(int l,int r,int id) {
if(L<=l&&r<=R) {
tr[id].Insert(x),ans+=tr[id].find2(x)-2,tr[id].Del(x);
return;
} int mid(l+((r-l)>>1));
if(L<=mid) find2(l,mid,id<<1);
if(mid<R) find2(mid+1,r,id<<1|1);
}
int kth() {
int l(0),r(1e8);
while(l<r) {
x=l+((r-l)>>1),ans=0,find2(1,n,1);
if(ans<k) l=x+1;
else r=x;
} return r;
}
vd pre(int l,int r,int id) {
if(L<=l&&r<=R) {
tr[id].Insert(x),ans=_max(ans,val[tr[id].pre()]),tr[id].Del(x);
return;
} int mid(l+((r-l)>>1));
if(L<=mid) pre(l,mid,id<<1);
if(mid<R) pre(mid+1,r,id<<1|1);
}
vd next(int l,int r,int id) {
if(L<=l&&r<=R) {
tr[id].Insert(x),ans=_min(ans,val[tr[id].next()]),tr[id].Del(x);
return;
} int mid(l+((r-l)>>1));
if(L<=mid) next(l,mid,id<<1);
if(mid<R) next(mid+1,r,id<<1|1);
}
vd Main() {
n=read(),m=read();
FOR(i,1,n) a[i]=read();
Build(1,n,1);
while(m--) {
switch(read()) {
case(1):L=read(),R=read(),x=read(),ans=0,find(1,n,1),write(ans+1);break;
case(2):L=read(),R=read(),k=read(),write(kth());break;
case(3):pos=read(),x=read(),up(1,n,1),a[pos]=x;break;
case(4):L=read(),R=read(),x=read(),ans=-INF,pre(1,n,1),write(ans);break;
case(5):L=read(),R=read(),x=read(),ans=INF,next(1,n,1),write(ans);break;
}
} fwrite(pbuf,1,pp-pbuf,stdout);
}
int main() {
Main();
return (0);
}
```
by 神迹 @ 2019-04-06 22:41:14
试图拯救以前的程序
by 神迹 @ 2019-04-06 22:41:34
QAQ
罕见的线段树套splay
我一般写线段树套fhq-treap
救不了你了QAQ
by CeLaMbDa @ 2019-04-06 22:42:55
虽然我后面还是水过去了- - 但是又打了一遍
by 神迹 @ 2019-04-06 22:45:00