压行版：
```cpp
#include<cstdio>
#include<cstdlib>
#include<ctime>
const int maxn=500001;
namespace treap{
int val[maxn],lc[maxn],rc[maxn],s[maxn],cnt;short key[maxn];
inline int newnode(int x){val[++cnt]=x,lc[cnt]=rc[cnt]=0,s[cnt]=1,key[cnt]=std::rand();return cnt;}
inline void pushup(int x){s[x]=s[lc[x]]+s[rc[x]]+1;}
void split(int rt,int&a,int&b,int x) {
if(!rt){a=b=0;return;}
if(val[rt]<=x){a=rt;split(rc[a],rc[a],b,x);}else{b=rt;split(lc[b],a,lc[b],x);}pushup(rt);
}
void merge(int&rt,int a,int b) {
if(!a||!b){rt=a|b;return;}
if(key[a]>key[b]){rt=a;merge(rc[rt],rc[rt],b);}else{rt=b;merge(lc[rt],a,lc[rt]);}pushup(rt);
}
inline void ins(int&rt,int x){int a,b;split(rt,a,b,x);merge(a,a,newnode(x));merge(rt,a,b);}
inline void del(int&rt,int x){int a,b;split(rt,a,b,x);split(a,a,rt,x-1);merge(rt,a,b);}
inline int query(int&rt,int l,int r){int a,b,ans;split(rt,a,b,r);split(a,a,rt,l-1);ans=s[rt];merge(a,a,rt);merge(rt,a,b);return ans;}
}
const int maxs=13500028;
int tree[maxs],ch[maxs][2],cnt=1,rt,L,R;
inline int newnode(){tree[cnt]=ch[cnt][0]=ch[cnt][1]=0;return cnt;}
inline void init(){rt=1,L=0,R=1e+8;}inline void move(int d){rt=ch[rt][0]?ch[rt][0]:ch[rt][0]=newnode();if(d)L=(L+R>>1)+1;else R=L+R>>1;}
inline void ins(int x,int y){for(init();treap::ins(tree[rt],y),L!=R;move((L+R>>1)<x));}
inline void del(int x,int y){for(init();treap::del(tree[rt],y),L!=R;move((L+R>>1)<x));}
inline int rank(int l,int r,int x){int ans=0;for(init();L!=R;move((L+R>>1)<x))if((L+R>>1)<x)ans+=treap::query(tree[rt],l,r);return ans;}
inline int kth(int l,int r,int k){int tmp=0,x;for(init();L!=R;move(tmp+x>k),tmp+=tmp+x>k?0:x)x=treap::query(tree[rt],l,r);return L;}
inline int pre(int l,int r,int x){int k=rank(l,r,x)-1;return k?kth(l,r,k):-2147483658;}
inline int nxt(int l,int r,int x){int k=rank(l,r,x+1);return k<=treap::query(tree[1],l,r)?kth(l,r,k):2147483647;}
int a[maxn],n,m,x,op,l,r;
int main() {
std::scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)std::scanf("%d",&a[i]),ins(i,a[i]);
for(;m;--m){
std::scanf("%d",&op);
switch(op){
case 1:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",kth(l,r,x));break;
case 2:std::scanf("%d%d",&l,&x);del(a[l],l);ins(x,l);a[l]=x;break;
case 3:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",rank(l,r,x));break;
case 4:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",pre(l,r,x));break;
default:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",nxt(l,r,x));break;
}
}
return 0;
}
```
by YamadaRyou @ 2021-06-11 12:58:36
不压行版（某位神仙帮我调的）：
```cpp
#include<cstdio>
#include<cstdlib>
#include<ctime>
const int maxn=500001;
namespace treap
{
int val[maxn],lc[maxn],rc[maxn],s[maxn],cnt;short key[maxn];
inline int newnode(int x)
{
val[++cnt]=x,
lc[cnt]=rc[cnt]=0,
s[cnt]=1,
key[cnt]=rand();
return cnt;
}
inline void pushup(int x)
{
s[x]=s[lc[x]]+s[rc[x]]+1;
}
void split(int rt,int&a,int&b,int x)
{
if(!rt){a=b=0;return;}
if(val[rt]<=x)
a=rt,split(rc[a],rc[a],b,x);
else
b=rt,split(lc[b],a,lc[b],x);
pushup(rt);
}
void merge(int&rt,int a,int b)
{
if(!a||!b){rt=a|b;return;}
if(key[a]>key[b])
rt=a,merge(rc[rt],rc[rt],b);
else
rt=b,merge(lc[rt],a,lc[rt]);
pushup(rt);
}
inline void ins(int&rt,int x)
{
int a,b;
split(rt,a,b,x);
merge(a,a,newnode(x));
merge(rt,a,b);
}
inline void del(int&rt,int x)
{
int a,b;split(rt,a,b,x);
split(a,a,rt,x-1);
merge(rt,a,b);
}
inline int query(int&rt,int l,int r)
{
int a,b,ans;
split(rt,a,b,r);
split(a,a,rt,l-1);
ans=s[rt];merge(a,a,rt);
merge(rt,a,b);
return ans;
}
}
const int maxs=13500028;
int tree[maxs],ch[maxs][2],cnt=1,rt,L,R;
inline int newnode()
{
tree[cnt]=ch[cnt][0]=ch[cnt][1]=0;
return cnt;
}
inline void init()
{
rt=1,L=0,R=1e+8;
}
inline void move(int d)
{
rt=ch[rt][0]?ch[rt][0]:ch[rt][0]=newnode();
if(d)L=(L+R>>1)+1;
else R=L+R>>1;
}
inline void ins(int x,int y)
{
for(init();treap::ins(tree[rt],y),L!=R;move((L+R>>1)<x));
}
inline void del(int x,int y)
{
for(init();treap::del(tree[rt],y),L!=R;move((L+R>>1)<x));
}
inline int rank(int l,int r,int x)
{
int ans=0;
for(init();L!=R;move((L+R>>1)<x))
if((L+R>>1)<x)
ans+=treap::query(tree[rt],l,r);
return ans;
}
inline int kth(int l,int r,int k)
{
int tmp=0,x;
for(init();L!=R;move(tmp+x>k),tmp+=tmp+x>k?0:x)
x=treap::query(tree[rt],l,r);
return L;
}
inline int pre(int l,int r,int x)
{
int k=rank(l,r,x)-1;
return k?kth(l,r,k):-2147483658;
}
inline int nxt(int l,int r,int x)
{
int k=rank(l,r,x+1);
return k<=treap::query(tree[1],l,r)?kth(l,r,k):2147483647;
}
int a[maxn],n,m,x,op,l,r;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),ins(i,a[i]);
for(;m;--m)
{
scanf("%d",&op);
switch(op)
{
case 1:
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",kth(l,r,x));
break;
case 2:
scanf("%d%d",&l,&x);
del(a[l],l);
ins(x,l);
a[l]=x;
break;
case 3:
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",rank(l,r,x));
break;
case 4:
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",pre(l,r,x));
break;
default:
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",nxt(l,r,x));
break;
}
}
return 0;
}
```
by YamadaRyou @ 2021-06-11 12:59:40
艹，发现主函数内每个操作的编号就错了，但修改完仍然过不了样例
by YamadaRyou @ 2021-06-11 13:18:30
我只会重构不会调
by lyhqwq @ 2021-06-13 15:41:11
我来了（
by lyhqwq @ 2021-07-31 22:53:36
还是不会
by lyhqwq @ 2021-07-31 22:54:25