你的求一个数的排名可能是这样写的:
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);
}
因为在递归求 rk 的时候树的形态会变。