fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. // generated at caterpillow.github.io/byot
  7.  
  8. namespace Treap {
  9.  
  10.     mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  11.     using ptr = struct Node*;
  12.  
  13.     struct Node {
  14.  
  15.         int key;
  16.         int sz;
  17.         int pri;
  18.         ptr l, r;
  19.  
  20.         Node() {
  21.             pri = mt();
  22.             sz = 1;
  23.             l = r = nullptr;
  24.         }
  25.  
  26.         Node(int key) : key(key) {
  27.             pri = mt();
  28.             sz = 1;
  29.             l = r = nullptr;
  30.         }
  31.     };
  32.  
  33.     int sz(ptr n) { return n ? n->sz : 0; };
  34.  
  35.     ptr pull(ptr n) {
  36.         if (!n) return nullptr;
  37.         n->sz = sz(n->l) + 1 + sz(n->r);
  38.         return n;
  39.     }
  40.  
  41.     ptr merge(ptr l, ptr r) {
  42.         if (!l || !r) return l ? l : r;
  43.         if (l->pri > r->pri) return l->r = merge(l->r, r), pull(l);
  44.         else return r->l = merge(l, r->l), pull(r);
  45.     }
  46.  
  47.     template<typename... Args>
  48.     ptr merge(ptr l, Args... args) {
  49.         return merge(l, merge(args...));
  50.     }
  51.  
  52.     // [-inf, i) and [i, inf]
  53.     pair<ptr, ptr> spliti(ptr n, int i) {
  54.         if (!n) return {nullptr, nullptr};
  55.         if (i <= sz(n->l)) {
  56.             auto [l, r] = spliti(n->l, i);
  57.             n->l = r;
  58.             return {l, pull(n)};
  59.         } else {
  60.             auto [l, r] = spliti(n->r, i - 1 - sz(n->l));
  61.             n->r = l;
  62.             return {pull(n), r};
  63.         }
  64.     }
  65.  
  66.     void heapify(ptr n) {
  67.         if (!n) return;
  68.         ptr mx = n;
  69.         if (n->l && n->l->pri > mx->pri) mx = n->l;
  70.         if (n->r && n->r->pri > mx->pri) mx = n->r;
  71.         if (mx != n) swap(n->pri, mx->pri), heapify(mx);
  72.     }
  73.  
  74.     ptr build(vector<ptr>& ns, int l = 0, int r = -69) {
  75.         if (r == -69) r = (int) ns.size() - 1;
  76.         if (l > r) return nullptr;
  77.         if (l == r) return ns[l];
  78.         int m = (l + r) / 2;
  79.         ns[m]->l = build(ns, l, m - 1);
  80.         ns[m]->r = build(ns, m + 1, r);
  81.         heapify(ns[m]);
  82.         return pull(ns[m]);
  83.     }
  84.  
  85.     template <typename Op>
  86.     void tour(ptr n, Op op) {
  87.         stack<ptr> stk;
  88.         while (n || !stk.empty()) {
  89.             for (; n; n = n->l) stk.push(n);
  90.             n = stk.top(); stk.pop();
  91.             op(n);
  92.             n = n->r;
  93.         }
  94.     }
  95.  
  96. }
  97.  
  98. using namespace Treap;
  99.  
  100. /*
  101.  
  102. - wrap in namespace
  103. - include n-way merge (and merge)
  104. - include split at index (and size)
  105. - include heapify + build
  106. - include tour
  107.  
  108. */
  109.  
  110. int n;
  111. ptr treap;
  112.  
  113. void random_shuffle(int a, int b) {
  114.     if (b < a) return;
  115.     int len = min(b - a, n - b);
  116.     int l0 = a;
  117.     int r0 = a + len;
  118.     int l1 = b;
  119.     int r1 = b + len;
  120.     auto [lxmy, r] = spliti(treap, r1);
  121.     auto [lxm, y] = spliti(lxmy, l1);
  122.     auto [lx, m] = spliti(lxm, r0);
  123.     auto [l, x] = spliti(lx, l0);
  124.     treap = Treap::merge(l, y, m, x, r); // merge with 5+ arguments requires namespace, since it conflicts with std::merge
  125. }
  126.  
  127. main() {
  128.     cin.tie(0)->sync_with_stdio(0);
  129.  
  130.     cin >> n;
  131.  
  132.     // O(n) build
  133.     vector<ptr> ns(n);
  134.     for (int i = 0; i < n; i++) ns[i] = new Node(i + 1);
  135.     treap = build(ns);
  136.  
  137.     for (int i = 0; i < n; i++) {
  138.         int a, b; cin >> a >> b;
  139.         random_shuffle(a - 1, b - 1);
  140.     }
  141.  
  142.     tour(treap, [&] (ptr n) { cout << n->key << ' '; });
  143. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4
3 1
1 3
3 2
2 3
stdout
copy 
3 1 4 2
https://ideone.com/Z20ZbE
3 1 4 2
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!