HYSBZ - 3224 Tyvj 1728 普通平衡树——splay

HYSBZ - 3224 Tyvj 1728 普通平衡树——splay

模板题，不过看了leaderboard后发现了更好的递归式splay，等下学一下

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;struct Splay_tree { int f[maxn], ch[maxn][2], key[maxn], cnt[maxn], size[maxn], sz, root; void clear() { sz = root = 0; } void init0(int x) { f[x] = ch[x][0] = ch[x][1] = key[x] = cnt[x] = size[x] = 0; } void init(int x, int fa, int v) { f[x] = fa; ch[x][0] = ch[x][1] = 0; key[x] = v; cnt[x] = size[x] = 1; } int witch(int x) { return ch[f[x]][1]==x; } void update(int x) { if (!x) return; size[x] = cnt[x]; if (ch[x][0]) size[x] += size[ch[x][0]]; if (ch[x][1]) size[x] += size[ch[x][1]]; } void rotate(int x) { int y = f[x], z = f[y], px = witch(x), py = witch(y); ch[y][px]=ch[x][px^1]; f[ch[y][px]] = y; ch[x][px^1]=y; f[y] = x; f[x]=z; if (z) ch[z][py]=x; update(y); update(x); } void splay(int x) { for (int fa; (fa = f[x]); rotate(x)) if (f[fa]) rotate(witch(x)==witch(fa)?fa:x); root = x; } void insert(int v) { if (!root) { init(++sz, 0, v); root = sz; return; } int fa = 0, now = root; while (true) { if (now == 0) { init(++sz, fa, v); ch[fa][key[fa] 1) { cnt[root]--; update(root); return; } if (!ch[root][0]&&!ch[root][1]) { init0(root); root = 0; return; } if (!ch[root][0]) { t = root; root = ch[root][1]; f[root] = 0; init0(t); return; } if (!ch[root][1]) { t = root; root = ch[root][0]; f[root] = 0; init0(t); return; } int p = pre(); t = root; splay(p); f[ch[t][1]] = root; ch[root][1] = ch[t][1]; init0(t); update(root); }}splay_tree;int main() { splay_tree.sz = 0, splay_tree.root = 0; int T; scanf("%d", &T); while (T--) { int opt, x; scanf("%d%d", &opt, &x); if (opt == 1) splay_tree.insert(x); else if (opt == 2) splay_tree.del(x); else if (opt == 3) printf("%d\n", splay_tree.find(x)); else if (opt == 4) printf("%d\n", splay_tree.findx(x)); else if (opt == 5) { splay_tree.insert(x); printf("%d\n", splay_tree.key[splay_tree.pre()]); splay_tree.del(x); } else { splay_tree.insert(x); printf("%d\n", splay_tree.key[splay_tree.next()]); splay_tree.del(x); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。