code:
```cpp
#include<bits/extc++.h>
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define all(x) x.begin(),x.end()
#define size(x) ((int)x.size())
#define ull unsigned long long
#define pii pair<int,int>
#define Inf (int)INFINITY
#define inf 2147483647
#define pb push_back
#define ll long long
#define endl '\n'
#define y second
#define x first
#define DEBUG
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
const int N=5e4+10,M=1<<20;
char buf[M],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,M,stdin),p1==p2)?EOF:*p1++)
void read(){};
template<class T1,class ...T2>
inline void read(T1& ret,T2&... rest){
ret=0;char c=getchar();bool f=false;
while(c<'0'||c>'9'){f=c=='-';c=getchar();}
while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
if(f)ret=-ret;
read(rest...);
}
#define cin(...) read(__VA_ARGS__)
char pbuf[M],*pp=pbuf;
#define putchar(c) *pp++=c;
inline void print(int ret){
static int sta[35];
int x=ret,top=0;
bool f=(ret<0);
if(ret<0) x=-x;
do{sta[top++]=x%10,x/=10;}while(x);
if(f) putchar('-');
while(top) putchar(sta[--top]+48);
putchar(endl);
}
int n,m,b[N];
struct Splay{
#define lc a[x].son[0]
#define rc a[x].son[1]
struct Node{
int val,cnt,siz,fa,son[2];
};
Splay(){
a.pb({0,0,0,0,{0,0}});
}
vector<Node> a;
int root=0,tot=0;
bool get(int x){
return a[a[x].fa].son[1]==x;
}
void connect(int x,int fa,bool way){
a[x].fa=fa;
a[fa].son[way]=x;
}
int build(int val,int fa){
a.pb({0,0,0,0,{0,0}});
a[++tot].val=val;
a[tot].cnt=a[tot].siz=1;
a[tot].fa=fa;
return tot;
}
void upd(int x){
a[x].siz=a[lc].siz+a[rc].siz+a[x].cnt;
}
bool empty(){
return root==0;
}
void rotate(int x){
int y=a[x].fa,z=a[y].fa;
bool way1=get(x),way2=get(y);
connect(a[x].son[!way1],y,way1);
connect(y,x,!way1);
connect(x,z,way2);
upd(y);
upd(x);
}
void splay(int x,int to){
to=a[to].fa;
while(a[x].fa!=to){
int y=a[x].fa;
if(a[y].fa==to) rotate(x);
else if(get(x)==get(y)){
rotate(y);
rotate(x);
}
else{
rotate(x);
rotate(x);
}
}
if(!to){
root=x;
}
}
int find(int val){
for(int x=root;;){
if(!x) return 0;
if(a[x].val==val){
splay(x,root);
return x;
}
x=a[x].son[val>a[x].val];
}
}
void insert(int val){
if(!root){
root=build(val,0);
return;
}
for(int x=root;;){
if(a[x].val==val){
a[x].cnt++;
splay(x,root);
return;
}
int way=(val>a[x].val);
if(!a[x].son[way]){
a[x].son[way]=build(val,x);
splay(x,root);
return;
}
x=a[x].son[way];
}
}
int join(int rt1,int rt2){
int x=rt1;
while(rc) x=rc;
splay(x,rt1);
connect(rt2,x,1);
upd(x);
return x;
}
void del(int val){
int x=find(val);
if(!x) return;
if(a[x].cnt>1){
a[x].cnt--;
a[x].siz--;
return;
}
if(!lc&&!rc){
root=0;
return;
}
if(!lc){
root=rc;
a[root].fa=0;
return;
}
int le=lc;
root=join(le,rc);
a[root].fa=0;
}
int getrank(int val){
insert(val);
int x=find(val);
int ans=a[lc].siz+1;
del(val);
return ans;
}
int pre(int val){
insert(val);
int x=find(val),now=lc;
if(!now) return -inf;
while(a[now].son[1]) now=a[now].son[1];
int ans=a[now].val;
del(val);
return ans;
}
int nxt(int val){
insert(val);
int x=find(val),now=rc;
if(!now) return inf;
while(a[now].son[0]) now=a[now].son[0];
int ans=a[now].val;
del(val);
return ans;
}
};
inline int lowbit(const int x){
return x&(-x);
}
struct Segtree{
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
struct Node{
int l,r;
Splay s;
}a[N<<2];
void build(int x,int l,int r){
a[x].l=l,a[x].r=r;
if(l==r){
int y=x;
while(y){
a[y].s.insert(b[l]);
y>>=1;
}
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
// cerr<<l<<" "<<r<<endl;
// cerr<<a[x].s.tot<<endl;
}
void del(int x,int pos,int val){
a[x].s.del(val);
if(a[x].l==a[x].r){
return;
}
int mid=(a[x].l+a[x].r)>>1;
if(pos<=mid){
del(ls,pos,val);
}
else{
del(rs,pos,val);
}
}
void add(int x,int pos,int val){
a[x].s.insert(val);
if(a[x].l==a[x].r){
return;
}
int mid=(a[x].l+a[x].r)>>1;
if(pos<=mid){
add(ls,pos,val);
}
else{
add(rs,pos,val);
}
}
int queryrnk(int x,int l,int r,int val){
// cerr<<a[x].l<<" "<<a[x].r<<" "<<val<<endl;
if(l<=a[x].l&&a[x].r<=r){
// cerr<<"\t"<<a[x].s.getrank(val)<<endl;
return a[x].s.getrank(val)-1;
}
int mid=(a[x].l+a[x].r)>>1,res=0;
if(l<=mid){
res+=queryrnk(ls,l,r,val);
}
if(mid<r){
res+=queryrnk(rs,l,r,val);
}
return res;
}
int pre(int x,int l,int r,int val){
if(l<=a[x].l&&a[x].r<=r){
// if(l==r){
// cerr<<val<<" "<<a[x].s.find(2)<<endl;
// }
return a[x].s.pre(val);
}
int mid=(a[x].l+a[x].r)>>1,res=-inf;
if(l<=mid){
res=max(res,pre(ls,l,r,val));
}
if(mid<r){
res=max(res,pre(rs,l,r,val));
}
return res;
}
int nxt(int x,int l,int r,int val){
if(l<=a[x].l&&a[x].r<=r){
return a[x].s.nxt(val);
}
int mid=(a[x].l+a[x].r)>>1,res=inf;
if(l<=mid){
res=min(res,nxt(ls,l,r,val));
}
if(mid<r){
res=min(res,nxt(rs,l,r,val));
}
return res;
}
inline int kth(int l,int r,int k){
int _l=0,_r=1e8+1;
while(_l+1<_r){
int mid=(_l+_r)/2;
if(queryrnk(1,l,r,mid)>=k){
_r=mid;
}
else{
_l=mid;
}
}
return _l;
}
}tr;
int main(){
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin(n,m);
for(int i=1;i<=n;i++){
cin(b[i]);
}
tr.build(1,1,n);
for(int op,l,r,pos,k,rnk;m;m--){
cin(op);
switch(op){
case 1:
cin(l,r,k);
print(tr.queryrnk(1,l,r,k)+1);
break;
case 2:
cin(l,r,k);
print(tr.kth(l,r,k));
break;
case 3:
cin(pos,k);
tr.del(1,pos,b[pos]);
tr.add(1,pos,k);
b[pos]=k;
break;
case 4:
cin(l,r,k);
rnk=tr.queryrnk(1,l,r,k);
if(rnk<1) print(-inf);
else print(tr.pre(1,l,r,k));
break;
case 5:
cin(l,r,k);
rnk=tr.queryrnk(1,l,r,k);
if(rnk>=(r-l+1)) print(inf);
else print(tr.nxt(1,l,r,k));
break;
}
}
fwrite(pbuf,1,pp-pbuf,stdout);
return 0;
}
```
input:
```
6 5
1 3 1 4 4 1
5 3 6 2
4 3 5 5
4 3 3 5
2 3 6 4
2 5 6 1
```
output:
```
4
4
1
4
1
```
my answer:
```
4
4
2
4
1
```
经检查发现,上面数据里第一次操作对平衡树产生影响,将它放到最后一次操作之后答案就对了,但是我没找出来哪里没删除干净。
by fangzichang @ 2023-07-10 19:48:24
try2码寄。
by fangzichang @ 2023-07-10 19:48:42
哈哈,我的splay里nxt和pre在没有找到的时候忘记删除了。
by fangzichang @ 2023-07-10 20:52:19