fork download
copy 
  1. // generated at caterpillow.github.io/byot
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6. using ll = long long;
  7.  
  8. // You can implement your own monoid here for custom operations.
  9. struct Value {
  10.     ll sum;
  11.  
  12.     Value operator+(const Value& oth) const {
  13.         Value res {};
  14.         res.sum = sum + oth.sum;
  15.         return res;
  16.     }
  17. };
  18.  
  19. const Value vid = {0};
  20.  
  21. mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  22. using ptr = struct Node*;
  23.  
  24. struct Node {
  25.     Value val;
  26.     Value agg;
  27.  
  28.     int sz;
  29.     int pri;
  30.     ptr l, r;
  31.     ptr par;
  32.  
  33.     Node() {
  34.         pri = mt();
  35.         val = vid;
  36.         agg = vid;
  37.         sz = 1;
  38.         l = r = nullptr;
  39.         par = nullptr;
  40.     }
  41.  
  42.     Node(Value val) : val(val), agg(val) {
  43.         pri = mt();
  44.         sz = 1;
  45.         l = r = nullptr;
  46.         par = nullptr;
  47.     }
  48.  
  49.     ~Node() {
  50.         delete l;
  51.         delete r;
  52.     }
  53. };
  54.  
  55. int sz(ptr n) { return n ? n->sz : 0; };
  56. Value agg(ptr n) { return n ? n->agg : vid; }
  57.  
  58. ptr pull(ptr n) {
  59.     if (!n) return nullptr;
  60.     if (n->l) n->l->par = n;
  61.     if (n->r) n->r->par = n;
  62.     n->sz = sz(n->l) + 1 + sz(n->r);
  63.     n->agg = agg(n->l) + n->val + agg(n->r);
  64.     return n;
  65. }
  66.  
  67. ptr merge(ptr l, ptr r) {
  68.     if (!l || !r) return l ? l : r;
  69.     if (l->pri > r->pri) return l->r = merge(l->r, r), pull(l);
  70.     else return r->l = merge(l, r->l), pull(r);
  71. }
  72.  
  73. // [-inf, i) and [i, inf]
  74. pair<ptr, ptr> spliti(ptr n, int i) {
  75.     if (!n) return {nullptr, nullptr};
  76.     n->par = nullptr;
  77.     if (i <= sz(n->l)) {
  78.         auto [l, r] = spliti(n->l, i);
  79.         n->l = r;
  80.         return {l, pull(n)};
  81.     } else {
  82.         auto [l, r] = spliti(n->r, i - 1 - sz(n->l));
  83.         n->r = l;
  84.         return {pull(n), r};
  85.     }
  86. }
  87.  
  88. ptr root(ptr n) {
  89.     while (n->par) n = n->par;
  90.     return n;
  91. }
  92.  
  93. /*
  94.  
  95. - include merge
  96. - include split by index (and size)
  97. - include range sum (and range aggregates, and values)
  98. - include root (and parent pointers)
  99.  
  100. */
  101.  
  102. main() {
  103.     cin.tie(0)->sync_with_stdio(0);
  104.  
  105.     int q; cin >> q;
  106.     map<int, ptr> nodes;
  107.     for (int i = 1; i <= q; i++) {
  108.         int t; cin >> t;
  109.         if (t == 1) {
  110.             int y; cin >> y;
  111.             nodes[i] = new Node({y});
  112.         }
  113.         if (t == 2) {
  114.             int y, z; cin >> y >> z;
  115.             ptr r1 = root(nodes[y]), r2 = root(nodes[z]);
  116.             if (r1 == r2) continue;
  117.             merge(r1, r2);
  118.         }
  119.         if (t == 3) {
  120.             int y, z; cin >> y >> z;
  121.             spliti(root(nodes[y]), z);
  122.         }
  123.         if (t == 4) {
  124.             int y; cin >> y;
  125.             cout << root(nodes[y])->agg.sum << '\n';
  126.         }
  127.     }
  128. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
10
1 38788
3 1 1
3 1 2
1 56200
3 1 2
3 1 2
4 4
3 4 4
4 1
3 4 6
stdout
copy 
56200
38788
https://ideone.com/BHPDWn
56200
38788
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!