警示后人(Splay 52pts,WA+RE)
查看原帖
警示后人(Splay 52pts,WA+RE)
427154
unsigned_short_int楼主2022/10/7 14:36
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询问排名时如果用了这种打法,请检查:

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改变,从而得出错误答案

2022/10/7 14:36
加载中...