splay写假了,应该是查找前驱后继后没有 Splay 操作,那么找前驱后继应该是把什么点旋转到根?
int get_prev(int u, int x)
{
if (!u) return -INF;
if (tr[u].v >= x) return get_prev(tr[u].s[0], x);
return max(tr[u].v, get_prev(tr[u].s[1], x));
}
int get_next(int u, int x)
{
if (!u) return INF;
if (tr[u].v <= x) return get_next(tr[u].s[1], x);
return min(tr[u].v, get_next(tr[u].s[0], x));
}
用的这个做法,显然里面没有 Splay 操作,但是貌似将前驱或后继所在的点 Splay 后还是 T 了