inline void find(int P,int k){
if(!k)return;
if(P==val[k]){
splay(k,0);
}else{
if(!son[k][P>val[k]])splay(k,0);
else find(P,son[k][P>val[k]]);
}return;
}
inline void find(int P,int k){
if(!k)return;
if(P==val[k]){
splay(k,0);
}else{
find(P,son[k][P>val[k]]);
}return;
}
下面的这份代码在平衡树模板TLE on #14,请问这是为什么? 这是我调用find函数的地方:
inline int pre(int P){
find(P,rt);int x=rt;
x=son[x][0];
while(son[x][1])x=son[x][1];
return x;
}
inline int nxt(int P){
find(P,rt);int x=rt;
x=son[x][1];
while(son[x][0])x=son[x][0];
return x;
}
且我在每次求x的前/后驱时,都插入了一个x
}else if(opt==5){
insert(x,rt,0);int res=pre(x);
cout<<val[res]<<'\n';
delet(x),splay(res,0);
}else if(opt==6){
insert(x,rt,0);int res=nxt(x);
cout<<val[res]<<'\n';
delet(x),splay(res,0);
}