警钟敲烂,如果你写Splay样例输出14
查看原帖
警钟敲烂,如果你写Splay样例输出14
790274
InQueue楼主2024/4/14 18:19

你的求一个数的排名可能是这样写的:

int rk(int x, int pr, int v)
	{
		if(!x)
		{
			splay(pr, 0);
			return 1;
		}
		if(v <= a[x].val)
		{
			return rk(a[x].l, x, v);
		}
		return rk(a[x].r, x, v) + a[a[x].l].sz + 1;//注意这里
	}

正确写法:

int rk(int x, int pr, int v)
	{
		if(!x)
		{
			splay(pr, 0);
			return 1;
		}
		if(v <= a[x].val)
		{
			return rk(a[x].l, x, v);
		}
		int tmp = a[a[x].l].sz + 1;
		return tmp + rk(a[x].r, x, v);
	}

因为在递归求 rkrk 的时候树的形态会变。

2024/4/14 18:19
加载中...