```cpp
/*---------------------------------Segment_Tree--------------------------------*/
#define lc ((x)<<1)
#define rc ((x)<<1|1)
#define mid ((l+r)>>1)
inline void Seg_Insert(int x,int l,int r,int pos,int val){
Splay_Insert(x,val);if(l==r)return;
if(pos<=mid)Seg_Insert(lc,l,mid,pos,val);
else Seg_Insert(rc,mid+1,r,pos,val);
}
inline void Seg_rank(int x,int l,int r,int L,int R,int Kth){
if(l==L&&r==R){ans+=Splay_rank(x,Kth);return;}
if(R<=mid)Seg_rank(lc,l,mid,L,R,Kth);
else if(mid<L)Seg_rank(rc,mid+1,r,L,R,Kth);
else Seg_rank(lc,l,mid,L,mid,Kth),Seg_rank(rc,mid+1,r,mid+1,R,Kth);
}
inline void Seg_change(int x,int l,int r,int pos,int val){
Splay_Delete(x,a[pos]);Splay_Insert(x,val);
if(l==r){a[pos]=val;return;}
if(pos<=mid)Seg_change(lc,l,mid,pos,val);
else Seg_change(rc,mid+1,r,pos,val);
}
inline void Seg_pre(int x,int l,int r,int L,int R,int val){
if(l==L&&r==R){ans=max(ans,Splay_Get_pre(x,val));return;}
if(R<=mid)Seg_pre(lc,l,mid,L,R,val);
else if(mid<L)Seg_pre(rc,mid+1,r,L,R,val);
else Seg_pre(lc,l,mid,L,mid,val),Seg_pre(rc,mid+1,r,mid+1,R,val);
}
inline void Seg_suc(int x,int l,int r,int L,int R,int val){
if(l==L&&r==R){ans=min(ans,Splay_Get_suc(x,val));return;}
if(R<=mid)Seg_suc(lc,l,mid,L,R,val);
else if(mid<L)Seg_suc(rc,mid+1,r,L,R,val);
else Seg_suc(lc,l,mid,L,mid,val),Seg_suc(rc,mid+1,r,mid+1,R,val);
}
/*----------------ask-------------*/
inline int Get_Kth(int x,int y,int k){
int L=0,R=MX+1,M;
while(L<R){
M=(L+R)>>1;
ans=0;Seg_rank(1,1,n,x,y,M);
if(ans<k)L=M+1;else R=M;
}return L-1;
}
/*-----------------Main--------------------*/
int main(){
IN(n),IN(m);null=new node ;null->siz=0;
// for(int i=1;i<=MAXN)
for(register int i=1;i<=n;++i){IN(a[i]);Seg_Insert(1,1,n,i,a[i]);MX=max(MX,a[i]);rt[i]=null;}
while(m--){
int op,x,y,v;IN(op),IN(x),IN(y);
switch(op){
case 1:{IN(v);ans=0;Seg_rank(1,1,n,x,y,v);printf("%d\n",ans+1);}break;
case 2:{IN(v);printf("%d\n",Get_Kth(x,y,v));}break;
case 3:{Seg_change(1,1,n,x,y);}break;
case 4:{IN(v);ans=-inf;Seg_pre(1,1,n,x,y,v);printf("%d\n",ans);}break;
case 5:{IN(v);ans=inf;Seg_suc(1,1,n,x,y,v);printf("%d\n",ans);}break;
}
}return 0;
}
```
by Bitter_ @ 2019-05-25 18:16:37
~~awsl~~
by 蒟蒻lxy @ 2019-05-25 20:54:03
ttttttttttttttttttttttttttttql
by bigju @ 2019-05-26 16:56:58
指针党一般没人帮你看Orz
@[R_h_DP](/space/show?uid=208881)
by TLE自动机 @ 2019-05-31 10:02:27
刚学就不应该学splay
by 2018LZY @ 2019-07-09 20:03:12