社区讨论

警示后人（Splay 52pts，WA+RE）

uunsigned_short_int
P6136【模板】普通平衡树（数据加强版）参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo7v90ga
此快照首次捕获于
2023/10/27 08:19
2 年前
此快照最后确认于
2023/10/27 08:19
2 年前
查看原帖
CPP
int getRank(const int &val,int p=root)
{
	if(!p)
		return 1;
	if(tr[p].val==val)
	{
		int res=tr[tr[p].ch[0]].siz+1;
		splay(p);
		return res;
	}
	if(tr[p].val<val)
		return tr[tr[p].ch[0]].siz+tr[p].cnt+getRank(val,tr[p].ch[1]);
	return getRank(val,tr[p].ch[0]);
}
Splay询问排名时如果用了这种打法，请检查：
CPP
return tr[tr[p].ch[0]].siz+tr[p].cnt+getRank(val,tr[p].ch[1]);
其中getRank函数需在tr[tr[p].ch[0]].siz之后，否则splay会改变树的形态，可能导致tr[tr[p].ch[0]].siz改变，从而得出错误答案。

回复

共 1 条回复，欢迎继续交流。

正在加载回复...