在本题中，似乎splay要比fhq优秀得多(我之前splay 70pts,只是WA),但splay很容易写错，而我重构代码写了fhq后，必须开$O(2)$才能过

那么问题来了

1. fhq是否是因为rand()，而效率欠佳
2. 如何优化这个fhq

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;
typedef long long ll;
int n,m,rt[maxn<<2],w[maxn],tot;
int a,b,c;
struct node
{
	int ch[2],si,pri,val;
}t[maxn<<7];

inline int read()
{
	int num,sign=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')sign=-1;
	num=c-'0';
	while((c=getchar())>='0'&&c<='9')
		num=(num<<1)+(num<<3)+c-'0';
	return num*sign;
}
int buf[15];
inline void write(int x)
{
	if(x<0)putchar('-');
	x=abs(x);
	int p=0;
	if(!x)buf[++p]=0;
	while(x)
	{
		buf[++p]=x%10;
		x/=10;
	}
	for(register int i=p;i;--i)putchar('0'+buf[i]);
	puts("");
}

inline void update(int x)
{
	t[x].si=t[t[x].ch[1]].si+t[t[x].ch[0]].si+1;
}

void split(int u,int k,int &a,int &b)
{
	if(!u)
	{
		a=b=0;
		return;
	}
	if(t[u].val<=k)
		a=u,split(t[u].ch[1],k,t[u].ch[1],b);
	else
		b=u,split(t[u].ch[0],k,a,t[u].ch[0]);
	update(u);
}

int merge(int a,int b)
{
	if(!a||!b)return a|b;
	if(t[a].pri<t[b].pri)
	{
		t[a].ch[1]=merge(t[a].ch[1],b);
		update(a);
		return a;
	}
	else
	{
		t[b].ch[0]=merge(a,t[b].ch[0]);
		update(b);
		return b;
	}
}

inline int newnode(int val)
{
	int u=++tot;
	t[tot].si=1;
	t[tot].val=val;
	t[tot].pri=rand();
	return u;
}

inline void insert(int k,int val)
{
	split(rt[k],val-1,a,b);
	rt[k]=merge(a,merge(newnode(val),b));
}

void build(int k,int l,int r)
{
	if(l==r)return insert(k,w[l]);
	for(register int i=l;i<=r;++i)insert(k,w[i]);
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}

int query(int k,int l,int r,int x,int y,int val)
{
	int res=0;
	if(l>=x&&r<=y)
	{
		split(rt[k],val-1,a,b);
		res=t[a].si;
		rt[k]=merge(a,b);
		return res;
	}
	int mid=(l+r)>>1;
	if(mid>=x)res+=query(k<<1,l,mid,x,y,val);
	if(mid<y)res+=query(k<<1|1,mid+1,r,x,y,val);
	return res;
}

inline void del_node(int k,int x)
{
	split(rt[k],x-1,a,b);
	split(b,x,c,b);
	c=merge(t[c].ch[0],t[c].ch[1]);
	rt[k]=merge(a,merge(c,b));
}

void modify(int k,int l,int r,int pos,int del_val,int val)
{
	del_node(k,del_val);
	insert(k,val);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(mid>=pos)modify(k<<1,l,mid,pos,del_val,val);
	else modify(k<<1|1,mid+1,r,pos,del_val,val);
}

int find_num(int u,int k)
{
	if(t[t[u].ch[0]].si+1==k)return t[u].val;
	if(t[t[u].ch[0]].si>=k)return find_num(t[u].ch[0],k);
	return find_num(t[u].ch[1],k-t[t[u].ch[0]].si-1);
}

int query_last(int k,int l,int r,int x,int y,int val)
{
	int res=-2147483647;
	if(l>=x&&r<=y)
	{
		split(rt[k],val-1,a,b);
		if(!t[a].si)res=-2147483647;
		else res=find_num(a,t[a].si);
		rt[k]=merge(a,b);
		return res;
	}
	int mid=(l+r)>>1;
	if(mid>=x)res=max(res,query_last(k<<1,l,mid,x,y,val));
	if(mid<y)res=max(res,query_last(k<<1|1,mid+1,r,x,y,val));
	return res;
}

int query_next(int k,int l,int r,int x,int y,int val)
{
	int res=2147483647;
	if(l>=x&&r<=y)
	{
		split(rt[k],val,a,b);
		if(!t[b].si)res=2147483647;
		else res=find_num(b,1);
		rt[k]=merge(a,b);
		return res;
	}
	int mid=(l+r)>>1;
	if(mid>=x)res=min(res,query_next(k<<1,l,mid,x,y,val));
	if(mid<y)res=min(res,query_next(k<<1|1,mid+1,r,x,y,val));
	return res;
}

int query_t(int k,int l,int r,int x,int y,int val)
{
	int res=0;
	if(l>=x&&r<=y)
	{
		split(rt[k],val,a,b);
		res=t[a].si;
		rt[k]=merge(a,b);
		return res;
	}
	int mid=(l+r)>>1;
	if(mid>=x)res+=query_t(k<<1,l,mid,x,y,val);
	if(mid<y)res+=query_t(k<<1|1,mid+1,r,x,y,val);
	return res;
}

inline int two_path(int l,int r,int k)
{
	int L=0,R=200000000;
	while(L<R)
	{
		int mid=(L+R)>>1;
		if(query_t(1,1,n,l,r,mid)<k)L=mid+1;
		else R=mid;
	}
	return R;
}

int main()
{
	srand(time(NULL));
	n=read(),m=read();
	for(register int i=1;i<=n;++i)w[i]=read();
	t[0].val=-1;
	build(1,1,n);
	for(register int pos,res,l,r,k,i=1;i<=m;++i)
	{
		res=read();
		if(res==1)
		{
			l=read(),r=read(),k=read();
			write(query(1,1,n,l,r,k)+1);
		}
		else if(res==2)
		{
			l=read(),r=read(),k=read();
			write(two_path(l,r,k));
		}
		else if(res==3)
		{
			pos=read(),k=read();
			modify(1,1,n,pos,w[pos],k);
			w[pos]=k;
		}
		else if(res==4)
		{
			l=read(),r=read(),k=read();
			write(query_last(1,1,n,l,r,k));
		}
		else
		{	
			l=read(),r=read(),k=read();
			write(query_next(1,1,n,l,r,k));
		}
	}
	return 0;
}