```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
}
template<typename T>inline void read(T&x,T&y,T&z){read(x),read(y),read(z);}
const int N=5e4+7;
const int INF=2147483647;
int rt[N<<2],A[N];
int tot,n,m,ql,qr,opt,maxval;//int cc=0;
//Splay
struct Splay_tree{
int ch[2],siz,cnt,val,fa;
}T[N*20*2];
inline int Get_pos(int x){return T[T[x].fa].ch[1]==x;}
inline void Pushup(int x){T[x].siz=T[x].cnt+T[T[x].ch[0]].siz+T[T[x].ch[1]].siz;}
inline void Rotate(int x){
int y=T[x].fa,z=T[y].fa,c=Get_pos(x);
T[y].ch[c]=T[x].ch[c^1],T[T[x].ch[c^1]].fa=y;
T[x].fa=z,T[z].ch[Get_pos(y)]=x;
T[y].fa=x,T[x].ch[c^1]=y;Pushup(y);
}
inline void Splay(int x,int to,int i){
int y=T[x].fa,z=T[y].fa;
while(y^to){
if(z^to)Get_pos(x)^Get_pos(y)?Rotate(x):Rotate(y);
Rotate(x);y=T[x].fa,z=T[y].fa;
}
if(!to)rt[i]=x;//T[0].ch[0]=T[0].ch[1]=0;
Pushup(x);
}
int Query_rank(int x,int val){
if(!x)return 0;
if(val<T[x].val)return Query_rank(T[x].ch[0],val);
else if(val==T[x].val)return T[T[x].ch[0]].siz;
return T[T[x].ch[0]].siz+T[x].cnt+Query_rank(T[x].ch[1],val);
}
int pre=0,suc=0;
int Query_pre(int x,int val){
if(!x)return -INF;
if(val<=T[x].val)return Query_pre(T[x].ch[0],val);
return pre=x,_max(T[x].val,Query_pre(T[x].ch[1],val));
}
int Query_suc(int x,int val){
if(!x)return INF;
if(val>=T[x].val)return Query_suc(T[x].ch[1],val);
return suc=x,_min(T[x].val,Query_suc(T[x].ch[0],val));
}
int Find(int x,int val){
if(!x)return 0;
if(val==T[x].val)return x;
return Find(T[x].ch[T[x].val<val],val);
}
inline void Splay_delete(int i,int val){
int x=Find(rt[i],val);Splay(x,0,i);
if(T[x].cnt>1){--T[x].cnt,--T[x].siz;return;}
if(!T[x].ch[0]||!T[x].ch[1]){rt[i]=T[x].ch[0]|T[x].ch[1],T[rt[i]].fa=0;return;}
Query_pre(x,val);Splay(pre,x,i);
rt[i]=pre,T[pre].ch[1]=T[x].ch[1],T[pre].fa=0,T[T[x].ch[1]].fa=pre;Pushup(pre);
}
inline void Ins(int&x,int val,int fa){
if(!x){T[x=++tot].val=val,T[x].siz=T[x].cnt=1,T[x].fa=fa;return;}
++T[x].siz;if(val==T[x].val){++T[x].cnt;return;}
Ins(T[x].ch[val>T[x].val],val,x);
}
inline void Splay_insert(int i,int val){int tmp=tot;Ins(rt[i],val,0);if(tmp^tot)Splay(tot,0,i);}
//Segment_tree
#define lc i<<1
#define rc i<<1|1
#define all 1,1,n
void Insert(int i,int L,int R,int pos){
Splay_insert(i,A[pos]);if(L==R)return;
int mid=L+R>>1;
pos<=mid?Insert(lc,L,mid,pos):Insert(rc,mid+1,R,pos);
}
int Rank(int i,int L,int R,int val){
if(ql<=L&&qr>=R)return Query_rank(rt[i],val);
int mid=L+R>>1,ret=0;
if(ql<=mid)ret+=Rank(lc,L,mid,val);
if(qr>mid)ret+=Rank(rc,mid+1,R,val);
return ret;
}
inline int Kth(int rk){
int L=0,R=maxval,mid;
while(L<R){
mid=L+R+1>>1;
if(Rank(all,mid)+1<=rk)L=mid;
else R=mid-1;
}
return L;
}
void Modify(int i,int L,int R,int pos,int val){
Splay_delete(i,A[pos]),Splay_insert(i,val);
if(L==R)return;int mid=L+R>>1;
pos<=mid?Modify(lc,L,mid,pos,val):Modify(rc,mid+1,R,pos,val);
}
int Ask_pre(int i,int L,int R,int val){
if(ql<=L&&qr>=R)return Query_pre(rt[i],val);
int ret=-INF,mid=L+R>>1;
if(ql<=mid)MAX(ret,Ask_pre(lc,L,mid,val));
if(qr>mid)MAX(ret,Ask_pre(rc,mid+1,R,val));
return ret;
}
int Ask_suc(int i,int L,int R,int val){
if(ql<=L&&qr>=R)return Query_suc(rt[i],val);
int ret=INF,mid=L+R>>1;
if(ql<=mid)MIN(ret,Ask_suc(lc,L,mid,val));
if(qr>mid)MIN(ret,Ask_suc(rc,mid+1,R,val));
return ret;
}
int k;
int main(){//freopen("tmp.in","r",stdin);freopen("ans.out","w",stdout);
read(n),read(m);
for(register int i=1;i<=n;++i)MAX(maxval,read(A[i])),Insert(all,i);
while(m--){
read(opt);
switch(opt){
case 1:read(ql,qr,k),printf("%d\n",Rank(all,k)+1);break;
case 2:read(ql,qr,k),printf("%d\n",Kth(k));break;
case 3:read(ql),MAX(maxval,read(k)),Modify(all,ql,k),A[ql]=k;break;
case 4:read(ql,qr,k),printf("%d\n",Ask_pre(all,k));break;
case 5:read(ql,qr,k),printf("%d\n",Ask_suc(all,k));break;
}
}
return 0;
}
```
by Ametsuji_akiya @ 2019-07-19 23:08:14
树套树！orz
by tanao @ 2019-07-20 01:04:07
这个常数大是没办法
只能怪写的丑
by sleepyNick @ 2019-07-20 09:01:09
还有那个read三个的是什么意思
没必要这样吧
by sleepyNick @ 2019-07-20 09:03:05
不是蓝名存在感低，而是数据结构难查，所以没人帮你查
by royzhu @ 2019-07-20 09:03:10
@[royzhu](/space/show?uid=35290) ~~德莱文好评~~
by guodong @ 2019-07-20 09:10:05
线段树套 fhq 哭出声
by VenusM1nT @ 2019-07-20 09:42:10
@[KajKeusaka](/space/show?uid=22658)
- 「只能怪写的丑」，您认为怎么写更优美or常数更小，我代码里哪些地方写的不好，还是说用splay本来就这样？还烦请指教。
- 我太菜了不会read读任意多个变量，所以就写了一个套3个read的函数。。如果您会的话可否教我一下写读任意多个变量的，在下感激不尽~~
by Ametsuji_akiya @ 2019-07-20 10:38:24