Splay [区间-数组模拟] 模板

#include <cstdio> #include <algorithm> const int N = 1e5 + 5; int n, a[N], tot, root; struct node { int v, s, c[2], fa, rev; node() { rev = v = fa = c[0] = c[1] = 0, s = 1; } node(int v, int fa) : v(v), fa(fa) { c[0] = c[1] = rev = 0; } } tr[N]; void up(int o) { tr[o].s = 1; if (tr[o].c[0]) tr[o].s += tr[tr[o].c[0]].s; if (tr[o].c[1]) tr[o].s += tr[tr[o].c[1]].s; } void down(int o) { if (!tr[o].rev) return; if (tr[o].c[0]) tr[tr[o].c[0]].rev ^= 1; if (tr[o].c[1]) tr[tr[o].c[1]].rev ^= 1; tr[o].rev = 0; std::swap(tr[o].c[0], tr[o].c[1]); } int son(int up, int down) { return down == tr[up].c[1]; } int build(int &o, int x[], int l, int r) { if (l > r) return 0; o = ++tot; if (l == r) { tr[o].v = x[l]; return o; } int mid = ceil((l + r) / 2.); tr[o].c[0] = build(tr[o].c[0], x, l, mid - 1); if (tr[o].c[0]) tr[tr[o].c[0]].fa = o; tr[o].c[1] = build(tr[o].c[1], x, mid, r); if (tr[o].c[1]) tr[tr[o].c[1]].fa = o; up(o); return o; } void rotate(int o) { int f = tr[o].fa, gf = tr[f].fa; if (!f) return; int d = son(f, o), gd = 0; if (gf) gd = son(gf, f); tr[f].c[d] = tr[o].c[d ^ 1]; if (tr[o].c[d ^ 1]) tr[tr[o].c[d ^ 1]].fa = f; tr[o].c[d ^ 1] = f; tr[f].fa = o; gf ? tr[gf].c[gd] = o : root = o; tr[o].fa = gf; } int search(int o, int k) { down(o); int s = 0; if (tr[o].c[0]) s = tr[tr[o].c[0]].s; if (k < s + 1) return search(tr[o].c[0], k); else if (k > s + 1) return search(tr[o].c[1], k - (s + 1)); else return o; } int at(int k) { return search(root, k); } void splay(int o, int t) { while (tr[o].fa != t) { int f = tr[o].fa, gf = tr[f].fa; if (gf == t) { rotate(o); break; } int d = son(f, o), gd = son(gf, f); d == gd ? rotate(f) : rotate(o); rotate(o); } } int main() { return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注