konchin_shih

Untitled

Aug 6th, 2020 (edited)
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.04 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<random>
  4. using namespace std;
  5. mt19937 mt;
  6. struct treap {
  7.     struct node {
  8.         int k, v, s;
  9.         node *l, *r;
  10.         node(int x): k(x), v(mt()), s(1) {l = r = nullptr;}
  11.         friend nodesize(node* x) {if (x) return x->s; else return 0;}
  12.         void pull() {s = 1 + nodesize(l) + nodesize(r);}
  13.     }*root;
  14.     treap(): root(nullptr) {}
  15.     int size() {return nodesize(root);}
  16.     void print(node* cur) {
  17.         if (!cur) return;
  18.         print(cur->l);
  19.         cout << cur->k << ' ';
  20.         print(cur->r);
  21.     }
  22.     void print() {
  23.         print(root), cout << endl;
  24.     }
  25.     node* merge(node* a, node* b) {
  26.         if (!a) return b;
  27.         if (!b) return a;
  28.         if (a->v < b->v)
  29.             return a->r = merge(a->r, b), a->pull(), a;
  30.         else
  31.             return b->l = merge(a, b->l), b->pull(), b;
  32.     }
  33.     void split_by_key(node* cur, int x, node*& a, node*& b) {
  34.         if (!cur) {a = b = nullptr; return;}
  35. //      cout << "split_by_key" << endl;
  36.         if (cur->k < x)
  37.             a = cur, split_by_key(a->r, x, a->r, b), a->pull();
  38.         else
  39.             b = cur, split_by_key(b->l, x, a, b->l), b->pull();
  40.     }
  41.     void insert(int x) {
  42.         node *l, *r;
  43.         split_by_key(root, x, l, r);
  44.         root = merge(merge(l, new node(x)), r);
  45.     }
  46.     void erase(int x) {
  47.         node *l, *m, *r;
  48.         split_by_key(root, x, l, r);
  49.         split_by_key(r, x + 1, m, r);
  50.         root = merge(merge(l, merge(m->l, m->r)), r);
  51.     }
  52.     void split_by_size(node* cur, int k, node*& a, node*& b) {
  53.         if (!cur) {a = b = nullptr; return;}
  54. //      cout << "split_by_size" << endl;
  55.         if (nodesize(cur->l) < k)
  56.             a = cur, split_by_size(a->r, k - nodesize(cur->l) - 1, a->r, b), a->pull();
  57.         else
  58.             b = cur, split_by_size(b->l, k, a, b->l), b->pull();
  59.     }
  60.     int find_by_order(int k) {
  61.         node *l, *m, *r;
  62.         split_by_size(root, k, l, r);
  63.         split_by_size(l, k - 1, l, m);
  64.         root = merge(l, merge(m, r));
  65.         return m->k;
  66.     }
  67. };
  68.  
  69. int main() {
  70.     treap s;
  71.     int op, k;
  72.     while (cin >> op >> k) {
  73.         switch (op) {
  74.         case 1:
  75.             s.insert(k);
  76.             break;
  77.         case 2:
  78.             s.erase(k);
  79.             break;
  80.         case 3:
  81.             cout << s.find_by_order(s.size() - k + 1) << endl;
  82.             break;
  83.         }
  84.         s.print();
  85.     }
  86.     return 0;
  87. }
Add Comment
Please, Sign In to add comment