splay函数写错了
by Xile @ 2024-01-29 11:21:56
@[rnfmabj5114](/user/917683) 还有插入时如果没有根的时候没有return
by Xile @ 2024-01-29 11:40:27
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,rt,m,v[100010],fa[100010],ch[100010][2],si[100010],cnt[100010];
int get(int x){
return x==ch[fa[x]][1];
}
void cesize(int x){
// cout << si[x] << si[ch[x][0]] << si[ch[x][1]] << '\n';
si[x]=si[ch[x][0]]+si[ch[x][1]]+cnt[x];
return ;
}
void clear(int x){
v[x]=fa[x]=ch[x][0]=ch[x][1]=si[x]=cnt[x]=0;
}
void rotate(int x){
int y=fa[x],z=fa[y],chtx=get(x),chty=get(y);
ch[y][chtx]=ch[x][chtx^1];
if(ch[x][chtx^1])
fa[ch[x][chtx^1]]=y;
ch[x][chtx^1]=y;
fa[y]=x;
fa[x]=z;
if(z)
ch[z][chty]=x;
cesize(y);
cesize(x);
return ;
}
void splay(int x){
for(int f;f=fa[x],f;rotate(x)){ // 定义f的时候不要=fa[x]， 不然就重复了
if(fa[f]){
if(get(x)!=get(f)){
rotate(x);
}
else{
rotate(f);
}
}
}
rt=x;
}
void cha(int x){
if(!rt){
n++;
v[n]=x;
cnt[n]++;
rt=n;
cesize(n);
return; //记得return
}
int cur=rt,f=0;
while(1){
if(v[cur]==x){
cnt[cur]++;
cesize(cur);
cesize(f);
splay(cur);
return ;
}
f=cur;
if(v[cur]<x)
cur=ch[f][1];
else
cur=ch[f][0];
if(!cur){
n++;
v[n]=x;
cnt[n]++;
fa[n]=f;
if(v[f]<x)
ch[f][1]=n;
else
ch[f][0]=n;
cesize(n);
cesize(f);
splay(n);
return ;
}
}
}
int kp(int x){
int tmp=0,cur=rt;
while(1){
if(x<v[cur]){
cur=ch[cur][0];
}
else{
tmp+=si[ch[cur][0]];
if(x==v[cur]){
splay(cur);
return tmp+1;
}
tmp+=cnt[cur];
cur=ch[cur][1];
}
}
}
int kth(int x){
int cur=rt;
while(1){
if(ch[cur][0]&&x<=si[ch[cur][0]]){
cur=ch[cur][0];
}
else{
x-=(si[ch[cur][0]]+cnt[cur]);
if(x<=0){
splay(cur);
return v[cur];
}
cur=ch[cur][1];
}
}
}
int qian(){
int cur=ch[rt][0];
if(!cur)
return cur;
while(ch[cur][1]){
cur=ch[cur][1];
}
splay(cur);
return cur;
}
int hou(){
int cur=ch[rt][1];
if(!cur)
return cur;
while(ch[cur][0])
cur=ch[cur][0];
splay(cur);
return cur;
}
void shan(int x){
kp(x);
if(cnt[rt]>1){
cnt[rt]--;
cesize(rt);
return;
}
if(!ch[rt][0]&&!ch[rt][1]){
clear(rt);
rt=0;
return;
}
if(!ch[rt][0]){
int cur=rt;
rt=ch[rt][1];
fa[rt]=0;
clear(cur);
return;
}
if(!ch[rt][1]){
int cur=rt;
rt=ch[rt][0];
fa[rt]=0;
clear(cur);
return;
}
int cur=rt,tmp=qian();
fa[ch[cur][1]]=tmp;
ch[tmp][1]=ch[cur][1];
clear(cur);
cesize(rt);
}
int main(){
cin>>m;
while(m--){
int op,x;
cin>>op;
if(op==1){
cin>>x;
cha(x);
}
if(op==2){
cin>>x;
shan(x);
}
if(op==3){
cin>>x;
cha(x);
cout<<kp(x)<<endl;
shan(x);
}
if(op==4){
cin>>x;
cout<<kth(x)<<endl;
}
if(op==5){
cin>>x;
cha(x);
cout<<v[qian()]<<endl;
shan(x);
}
if(op==6){
cin>>x;
cha(x);
cout<<v[hou()]<<endl;
shan(x);
}
// for (int i = 1; i <= n; i++) cout << ch[i][0] << " " << ch[i][1] << " " << v[i] << " " << si[i] << "--\n";
}
}
/*
4
1 10
1 30
1 20
3 21
*/
```
by Xile @ 2024-01-29 11:42:05
好吧其实splay那里不用改也可以过
by Xile @ 2024-01-29 11:44:48