Mlxa

Неявный splay

Sep 13th, 2020
894
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node {
  5.     int l = 0, r = 0, p = 0, k = 0, s = 0;
  6. } t[1001000];
  7. int ptr = 1;
  8. int new_node(int k) {
  9.     int v = ptr++;
  10.     t[v].s = 1;
  11.     t[v].k = k;
  12.     return v;
  13. }
  14. void pull(int v) {
  15.     t[v].s = t[t[v].l].s + 1 + t[t[v].r].s;
  16. }
  17. int &son(int v, int i) {
  18.     return i ? t[v].r : t[v].l;
  19. }
  20. void rot(int v) {
  21.     int p = t[v].p, g = t[p].p;
  22.     assert(v != p && v != g);
  23.     int sv = t[p].r == v, sp = t[g].r == p;
  24.     int &u = son(v, sv ^ 1);
  25.     son(p, sv) = u, t[u].p = p, pull(p);
  26.     u = p, t[p].p = v, pull(v);
  27.     if (g) {
  28.         son(g, sp) = v, t[v].p = g, pull(g);
  29.     } else {
  30.         t[v].p = 0;
  31.     }
  32. }
  33. void splay(int v) {
  34.     while (t[v].p) {
  35.         int p = t[v].p, g = t[p].p;
  36.         if (!g) {
  37.             rot(v);
  38.         } else if ((v == t[p].r) == (p == t[g].r)) {
  39.             rot(p), rot(v);
  40.         } else {
  41.             rot(v), rot(v);
  42.         }
  43.     }
  44. }
  45. int by_order(int v, int k) {
  46.     while (1) {
  47.         int l = t[v].l;
  48.         if (k < t[l].s) {
  49.             v = t[v].l;
  50.         } else if (k > t[l].s) {
  51.             k -= t[l].s + 1;
  52.             v = t[v].r;
  53.         } else {
  54.             splay(v);
  55.             return v;
  56.         }
  57.     }
  58. }
  59. void print(int v) {
  60.     if (v) {
  61.         print(t[v].l);
  62.         cout << t[v].k << " ";
  63.         print(t[v].r);
  64.     }
  65. }
  66. signed main() {
  67. #ifdef LC
  68.     assert(freopen("input.txt", "r", stdin));
  69. #endif
  70.     ios::sync_with_stdio(0);
  71.     cin.tie(0);
  72.     int n, x, v = 0, u;
  73.     cin >> n;
  74.     n = 0;
  75.     for (string s; cin >> s; ) {
  76.         if (s == "add") {
  77.             cin >> x;
  78.             u = new_node(x);
  79.             if (n) {
  80.                 v = by_order(v, n - 1);
  81.                 t[v].r = u, t[u].p = v, pull(v);
  82.             } else {
  83.                 v = u;
  84.             }
  85.             ++n;
  86.         } else if (s == "take") {
  87.             if (n >= 2) {
  88.                 v = by_order(v, n - 2);
  89.                 t[v].r = 0, pull(v);
  90.                 --n;
  91.             } else {
  92.                 v = 0, n = 0;
  93.             }
  94.         } else if (n >= 2) {
  95.             v = by_order(v, n / 2 - 1), u = t[v].r;
  96.             t[v].r = 0, t[u].p = 0, pull(v);
  97.             v = by_order(v, 0), u = by_order(u, t[u].s - 1);
  98.             t[v].l = u, t[u].p = v, pull(v);
  99.         }
  100.     }
  101.     cout << n << endl;
  102.     print(v);
  103.     return 0;
  104. }
  105.  
RAW Paste Data