peltorator

!Персистентное Декартово Дерево

Jul 15th, 2017
272
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. typedef long long ll;
  5. typedef double ld;
  6.  
  7. #define fastRead cin.sync_with_stdio(0); cin.tie(0); cout.tie(0)
  8. #define in(s) freopen(s, "r", stdin);
  9. #define out(s) freopen(s, "w", stdout);
  10. #define fi first
  11. #define se second
  12.  
  13. struct Node
  14. {
  15.     int x;
  16.     ll sum;
  17.     int size;
  18.     Node *left;
  19.     Node *right;
  20.     Node(int x):
  21.         x(x),
  22.         sum(x),
  23.         size(1),
  24.         left(0),
  25.         right(0) {}
  26. };
  27.  
  28. int size(Node *v)
  29. {
  30.     return (v == NULL ? 0 : v->size);
  31. }
  32.  
  33. ll sum(Node *v)
  34. {
  35.     return (v == NULL ? 0 : v->sum);
  36. }
  37.  
  38. void upd(Node *v)
  39. {
  40.     if (!v)
  41.         return;
  42.     v->sum = v->x + sum(v->left) + sum(v->right);
  43.     v->size = 1 + size(v->left) + size(v->right);
  44. }
  45.  
  46. pair<Node*, Node*> split(Node *v, int s)
  47. {
  48.     if (!v)
  49.         return {v, v};
  50.     if (!s)
  51.         return {0, v};
  52.     Node *t = new Node(v->x);
  53.     if (size(v->left) >= s)
  54.     {
  55.         pair<Node*, Node*> a = split(v->left, s);
  56.         t->left = a.second;
  57.         t->right = v->right;
  58.         upd(t);
  59.         return {a.first, t};
  60.     }
  61.     pair<Node*, Node*> a = split(v->right, s - 1 - size(v->left));
  62.     t->right = a.first;
  63.     t->left = v->left;
  64.     upd(t);
  65.     return {t, a.second};
  66. }
  67.  
  68. pair<Node*, Node*> split1(Node *v, int s)
  69. {
  70.     if (!v)
  71.         return {v, v};
  72.     if (!s)
  73.         return {0, v};
  74.     if (size(v->left) >= s)
  75.     {
  76.         pair<Node*, Node*> a = split1(v->left, s);
  77.         v->left = a.second;
  78.         upd(v);
  79.         return {a.first, v};
  80.     }
  81.     pair<Node*, Node*> a = split1(v->right, s - 1 - size(v->left));
  82.     v->right = a.first;
  83.     upd(v);
  84.     return {v, a.second};
  85. }
  86.  
  87. Node* merge(Node *l, Node *r)
  88. {
  89.     if (!l)
  90.         return r;
  91.     if (!r)
  92.         return l;
  93.     int a = (rand() << 16) + rand();
  94.     a %= (size(l) + size(r));
  95.     if (a < size(l))
  96.     {
  97.         Node *L = new Node(l->x);
  98.         Node *q = merge(l->right, r);
  99.         upd(q);
  100.         L->left = l->left;
  101.         L->right = q;
  102.         upd(L);
  103.         return L;
  104.     }
  105.     Node *R = new Node(r->x);
  106.     Node *q = merge(l, r->left);
  107.     upd(q);
  108.     R->right = r->right;
  109.     R->left = q;
  110.     upd(R);
  111.     return R;
  112. }
  113.  
  114. Node* merge1(Node *l, Node *r)
  115. {
  116.     if (!l)
  117.         return r;
  118.     if (!r)
  119.         return l;
  120.     int a = (rand() << 16) + rand();
  121.     a %= (size(l) + size(r));
  122.     if (a < size(l))
  123.     {
  124.         Node *q = merge1(l->right, r);
  125.         upd(q);
  126.         l->right = q;
  127.         upd(l);
  128.         return l;
  129.     }
  130.     Node *q = merge1(l, r->left);
  131.     upd(q);
  132.     r->left = q;
  133.     upd(r);
  134.     return r;
  135. }
  136.  
  137. void gogo(Node *v)
  138. {
  139.     if (!v)
  140.         return;
  141.     gogo(v->left);
  142.     cout << v->x << " ";
  143.     gogo(v->right);
  144. }
  145.  
  146. int main()
  147. {
  148.     in("memory.in");
  149.     out("memory.out");
  150.     fastRead;
  151.     int n;
  152.     cin >> n;
  153.     ll x, a, b, m;
  154.     cin >> x >> a >> b >> m;
  155.     Node *root = new Node(x);
  156.     for (int i = 2; i <= n; i++)
  157.     {
  158.         x = (x * a + b) % m;
  159.         root = merge1(root, new Node(x));
  160.     }
  161.     int k;
  162.     cin >> k;
  163.     for (int i = 0; i < k; i++)
  164.     {
  165.         string s;
  166.         cin >> s;
  167.         if (s == "sum")
  168.         {
  169.             int l, r;
  170.             cin >> l >> r;
  171.             auto a = split(root, r);
  172.             auto b = split(a.first, l - 1);
  173.             cout << sum(b.second) << "\n";
  174.             root = merge(b.first, merge(b.second, a.second));
  175.         }
  176.         else if (s == "out")
  177.         {
  178.             int l, r;
  179.             cin >> l >> r;
  180.             auto a = split(root, r);
  181.             auto b = split(a.first, l - 1);
  182.             gogo(b.second);
  183.             root = merge(b.first, merge(b.second, a.second));
  184.             cout << "\n";
  185.         }
  186.         else
  187.         {
  188.             int aa, bb, l;
  189.             cin >> aa >> bb >> l;
  190.             auto a = split(root, aa - 1);
  191.             auto b = split(a.second, l);
  192.             a = split(root, bb - 1);
  193.             auto c = split(a.second, l);
  194.             root = merge(a.first, merge(b.first, c.second));
  195.         }
  196.     }
  197.     return 0;
  198. }
RAW Paste Data