Advertisement
gt22

Untitled

May 1st, 2020
741
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.09 KB | None | 0 0
  1.  
  2. #include "optimization.h"
  3.  
  4. int allocator_pos = 0;
  5. char allocator_memory[1000000000];
  6.  
  7. void *operator new(size_t n) {
  8.     char *res = allocator_memory + allocator_pos;
  9.     allocator_pos += n;
  10.     return (void *) res;
  11. }
  12.  
  13. void operator delete(void *) noexcept {}
  14. #include <vector>
  15.  
  16. using namespace std;
  17.  
  18. long long U = 35345312, L = 512313;
  19. unsigned long long cur = 0;
  20. inline unsigned long long nextRand24() {
  21.     cur = cur * U + L;
  22.     return cur >> 8u;
  23. }
  24.  
  25. struct Node;
  26.  
  27. inline int s(Node *n) noexcept;
  28.  
  29. inline size_t ss(Node *n) noexcept;
  30.  
  31. struct Node {
  32.     int x;
  33.     Node *l, *r;
  34.     int size = -1;
  35.     size_t sum = -1;
  36.  
  37.  
  38.     Node(size_t x, Node *l = nullptr, Node *r = nullptr) : x(x), l(l), r(r) { recalc(); }
  39.  
  40.     Node *withLeft(Node *nl) noexcept {
  41.         return new Node(x, nl, r);
  42.     }
  43.  
  44.     Node *withRight(Node *nr) noexcept {
  45.         return new Node(x, l, nr);
  46.     }
  47.  
  48.     void recalc() noexcept {
  49.         size = s(l) + s(r) + 1;
  50.         sum = ss(l) + ss(r) + x;
  51.     }
  52.  
  53.     void full_recalc() noexcept {
  54.         if(l) l->full_recalc();
  55.         if(r) r->full_recalc();
  56.         recalc();
  57.     }
  58.  
  59. };
  60.  
  61. inline int s(Node *n) noexcept {
  62.     return n ? n->size : 0;
  63. }
  64.  
  65. inline size_t ss(Node *n) noexcept {
  66.     return n ? n->sum : 0;
  67. }
  68.  
  69. inline int index(Node *n) noexcept {
  70.     Node *l = n->l;
  71.     return l ? l->size + 1 : 1;
  72. }
  73.  
  74. pair<Node *, Node *> split(Node *t, int i) noexcept {
  75.     if (!t) {
  76.         return {nullptr, nullptr};
  77.     } else if (index(t) < i) {
  78.         auto[a, b] = split(t->r, i - index(t));
  79.         return {t->withRight(a), b};
  80.     } else {
  81.         auto[a, b] = split(t->l, i);
  82.         return {a, t->withLeft(b)};
  83.     }
  84. }
  85.  
  86. Node *merge(Node *l, Node *r) noexcept {
  87.     if (!l || !r) return l ? l : r;
  88.     else if (nextRand24() * r->size < nextRand24() * l->size) {
  89.         return l->withRight(merge(l->r, r));
  90.     } else {
  91.         return r->withLeft(merge(l, r->l));
  92.     }
  93. }
  94.  
  95. void print(Node *t, int l, int r) noexcept {
  96.     if (!t || r <= l || r <= 0) return;
  97.     int i = index(t);
  98.     print(t->l, l, min(i, r));
  99.     if (l <= i && i < r) writeInt(t->x, ' ');
  100.     print(t->r, max(l - i, 0), r - i);
  101. }
  102.  
  103. size_t sum(Node *t, int l, int r) noexcept {
  104.     if (!t || r <= l || r <= 0) return 0;
  105.     if (l <= 1 && r > t->size) return t->sum;
  106.     int i = index(t);
  107.     size_t s = 0;
  108.     s += sum(t->l, l, r);
  109.     if (l <= i && i < r) s += t->x;
  110.     s += sum(t->r, max(l - i, 0), r - i);
  111.     return s;
  112. }
  113.  
  114. Node *build(const vector<int>& v, int l, int r) {
  115.     if(r <= l) return nullptr;
  116.     if(l == r - 1) return new Node(v[l]);
  117.     int m = (l + r) / 2;
  118.     Node *nn = new Node(v[m]);
  119.     nn->l = build(v, l, m);
  120.     nn->r = build(v, m + 1, r);
  121.     nn->recalc();
  122.     return nn;
  123. }
  124.  
  125. int main() {
  126.     int n = readInt();
  127.     size_t X = readInt<size_t>(), A = readInt<size_t>(), B = readInt<size_t>(), M = readInt<size_t>();
  128.     vector<int> xs;
  129.     xs.reserve(n);
  130.     xs.push_back(X);
  131.     for (int i = 1; i < n; ++i) {
  132.         X = (A * X + B);
  133.         if(X > M) X %= M;
  134.         xs.push_back(X);
  135.     }
  136.     Node *root = build(xs, 0, n);
  137.     int k = readInt();
  138.     for (int j = 0; j < k; ++j) {
  139.         int c = readChar();
  140.         readChar();
  141.         readChar();
  142.         switch (c) {
  143.             case 'o': { //out
  144.                 int l = readInt(), r = readInt();
  145.                 print(root, l, r + 1);
  146.                 writeChar('\n');
  147.                 break;
  148.             }
  149.             case 'c': { //cpy
  150.                 int a = readInt(), b = readInt(), l = readInt();
  151.                 auto[A1, T1] = split(root, a);
  152.                 auto[B1, C1] = split(T1, a + l - s(A1));
  153.                 auto[A2, T2] = split(root, b);
  154.                 auto[B2, C2] = split(T2, b + l - s(A2));
  155.                 root = merge(merge(A2, B1), C2);
  156.                 break;
  157.             }
  158.             case 's': { //sum
  159.                 int l = readInt(), r = readInt() + 1;
  160.                 writeInt(sum(root, l, r), '\n');
  161.                 break;
  162.             }
  163.             default:
  164.                 assert(false);
  165.         }
  166.     }
  167.     return 0;
  168. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement