在本题唯一的splay题解中,我对
inline int find(const int& x){
int now=root,res=0;
while(true){
pushdown(now);
if(x<=Max[ch[now][0]])
now=ch[now][0];
else{
res+=size[ch[now][0]];
if(x<=val[now])
return res+1;
++res;
now=ch[now][1];
}
}
return -1;
}
并不是非常理解。
另外,本题用splay维护的是区间,中序遍历是原序列,而不是平衡树,此篇题解是如何做到
- 找到值为 v 的节点
- splay min和max, 保证此时max节点的左儿子的子树中的数都是大于等于min小于等于max的?