```cpp
//树套树
#include<bits/stdc++.h>
using namespace std;
#define lc (u<<1)
#define rc (u<<1|1)
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
#define inf 0x7fffffff
#define N 500009
#define auto int
inline auto read(){
auto x=0,f=1;
auto c='\0';
for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
class node{
public:
int s[2],fa,val,size;
node()=default;
void init(int p,int v){fa=p,val=v,size=1;}
}tr[N*40];
//unordered_map<int,int>w,root;
//unordered_map<int,node>tr;
int w[N],root[N*10];
int n,m,idx,op,x,l,r,pos,k,ans;
inline void pushup(auto x){
tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}
inline void rotate(auto x){//旋转※包括左旋和右旋
auto y=tr[x].fa,z=tr[y].fa;//y=father;z=grandfather
auto k=tr[y].s[1]==x;//k=x is y's which son
tr[y].s[k]=tr[x].s[k^1];
tr[tr[x].s[k^1]].fa=y;
tr[x].s[k^1]=y;
tr[y].fa=x;
tr[z].s[tr[z].s[1]==y]=x;
tr[x].fa=z;
pushup(y),pushup(x);
}
inline void splay(auto &root,auto x,auto k){//伸展※核心 （目标：使x成为k的儿子）
while(tr[x].fa!=k){
auto y=tr[x].fa,z=tr[y].fa;
if(z!=k)
if((tr[y].s[0]==x&&tr[y].s[0]!=y)||(tr[y].s[0]!=x&&tr[y].s[0]==y))rotate(x);
else rotate(y);
rotate(x);
}
if(k==0)root=x;
}
void insert(auto &root,auto v){
auto u=root,p=0;
while(u)p=u,u=tr[u].s[v>tr[u].val];
u=++idx;
tr[p].s[v>tr[p].val]=u;
tr[u].init(p,v);
splay(root,u,0);
}
void build(auto u,auto l,auto r){
insert(root[u],-inf),insert(root[u],inf);
for(int i=l;i<=r;i++)insert(root[u],w[i]);
if(l==r)return;
auto mid=(l+r)>>1;
build(lc,l,mid),build(rc,mid+1,r);
}
auto getrank(int root,int v){
auto u=root,ret=0;
while(u){
if(tr[u].val<v)ret+=tr[ls(u)].size+1,u=rs(u);
else u=ls(u);
}return ret;
}
auto queryrank(auto u,int l,int r,auto x,auto y,int v){
if(x<=l&&r<=y)return getrank(root[u],v)-1;
auto mid=(l+r)>>1,ret=0;
if(x<=mid)ret+=queryrank(lc,l,mid,x,y,v);
if(y>mid)ret+=queryrank(rc,mid+1,r,x,y,v);
return ret;
}
auto queryval(auto u,auto x,auto y,auto k){
auto l=0,r=inf,ans=0;
while(l<=r){
auto mid=(l+r)>>1;
if(queryrank(1,1,n,x,y,mid)+1<=k)l=mid+1,ans=mid;
else r=mid-1;
}return ans;
}
void del(auto &root,auto v){
auto u=root;
while(u){
if(tr[u].val==v)break;
if(tr[u].val<v)u=rs(u);
else u=ls(u);
}
splay(root,u,0);
auto l=ls(u),r=rs(u);
while(rs(l))l=rs(l);
while(ls(r))r=ls(r);
splay(root,l,0);
splay(root,r,l);
ls(r)=0;
splay(root,r,0);
}
void change(auto u,auto l,auto r,auto pos,auto v){
del(root[u],w[pos]);
insert(root[u],v);
if(l==r)return;
auto mid=(l+r)>>1;
if(pos<=mid)change(lc,l,mid,pos,v);
else change(rc,mid+1,r,pos,v);
}
auto getpre(auto root,auto v){
auto u=root,ret=-inf;
while(u){
if(tr[u].val<v)ret=tr[u].val,u=rs(u);
else u=ls(u);
}return ret;
}
auto querypre(auto u,auto l,auto r,auto x,auto y,auto v){
if(x<=l&&r<=y)return getpre(root[u],v);
auto mid=(l+r)>>1,ret=-inf;
if(x<=mid)ret=max(ret,querypre(lc,l,mid,x,y,v));
if(y>mid)ret=max(ret,querypre(rc,mid+1,r,x,y,v));
return ret;
}
auto getnxt(auto root,auto v){
auto u=root,ret=inf;
while(u){
if(tr[u].val>v)ret=tr[u].val,u=ls(u);
else u=rs(u);
}return ret;
}
auto querynxt(auto u,auto l,auto r,auto x,auto y,auto v){
if(x<=l&&r<=y)return getnxt(root[u],v);
auto mid=(l+r)>>1,ret=inf;
if(x<=mid)ret=min(ret,querynxt(lc,l,mid,x,y,v));
if(y>mid)ret=min(ret,querynxt(rc,mid+1,r,x,y,v));
return ret;
}
signed main(){
// freopen("P3380_8.in","r",stdin);
n=read(),m=read();
for(int i=1;i<=n;i++)w[i]=read();
build(1,1,n);
while(m--){
op=read();
switch(op){
case 1:l=read(),r=read(),k=read(),printf("%d\n",queryrank(1,1,n,l,r,k)+1);break;
case 2:l=read(),r=read(),k=read(),printf("%d\n",queryval(1,l,r,k));break;
case 3:pos=read(),k=read(),change(1,1,n,pos,k);w[pos]=k;break;
case 4:l=read(),r=read(),k=read(),printf("%d\n",querypre(1,1,n,l,r,k));break;
case 5:l=read(),r=read(),k=read(),printf("%d\n",querynxt(1,1,n,l,r,k));break;
default:throw("ERROR! Read the wrong op!");
}
}
}
```
by wangbinfeng @ 2023-12-26 22:17:59
为啥有人发生日快乐都没人理我呀？哭了
by wangbinfeng @ 2023-12-26 22:28:11
又在机房拖了半小时，要回家了qwq
15min后统一回复
谢谢大佬啦
by wangbinfeng @ 2023-12-26 22:30:58