对题解的疑惑
查看原帖
对题解的疑惑
685604
Neovim楼主2023/4/15 22:58

在本题唯一的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维护的是区间,中序遍历是原序列,而不是平衡树,此篇题解是如何做到

  • 找到值为 vv 的节点
  • splay minmin和maxmax, 保证此时maxmax节点的左儿子的子树中的数都是大于等于minmin小于等于maxmax的?
2023/4/15 22:58
加载中...