gt22

Untitled

May 2nd, 2020
621
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.13 KB | None | 0 0
  1.  
  2.  
  3.  
  4. #include "optimization.h"
  5.  
  6. int allocator_pos = 0;
  7. char allocator_memory[1000000000];
  8. #include <tuple>
  9. #include <vector>
  10. #include <random>
  11.  
  12. using namespace std;
  13.  
  14. int U = 4321, L = 54321;
  15. unsigned int cur = 0;
  16. std::mt19937 gen(234);
  17. inline size_t nextRand24() {
  18. //    cur = cur * U + L;
  19. //    return cur >> 8u;
  20.     return gen();
  21. }
  22.  
  23. struct Node;
  24.  
  25. int s(Node *n) noexcept;
  26.  
  27. size_t ss(Node *n) noexcept;
  28.  
  29. struct Node {
  30.     int x;
  31.     Node *l, *r;
  32.     int size = -1;
  33.     int depth = -1;
  34.     size_t sum = -1;
  35.  
  36.  
  37.     Node(size_t x, Node *l = nullptr, Node *r = nullptr) : x(x),
  38.                                                            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.     Node *mutateLeft(Node *nl) {
  49.         l = nl;
  50.         recalc();
  51.         return this;
  52.     }
  53.  
  54.     Node *mutateRight(Node *nr) {
  55.         r = nr;
  56.         recalc();
  57.         return this;
  58.     }
  59.  
  60.     void recalc() noexcept {
  61.         size = s(l) + s(r) + 1;
  62.         sum = ss(l) + ss(r) + x;
  63.         depth = max(l ? l->depth : 0, r ? r->depth : 0) + 1;
  64.     }
  65.  
  66.     void full_recalc() noexcept {
  67.         if(l) l->full_recalc();
  68.         if(r) r->full_recalc();
  69.         recalc();
  70.     }
  71.  
  72.     void *operator new(size_t n) {
  73.         char *res = allocator_memory + allocator_pos;
  74.         allocator_pos += n;
  75.         return (void *) res;
  76.     }
  77.  
  78.     void operator delete(void *) noexcept {}
  79.  
  80. };
  81.  
  82. int s(Node *n) noexcept {
  83.     return n ? n->size : 0;
  84. }
  85.  
  86. size_t ss(Node *n) noexcept {
  87.     return n ? n->sum : 0;
  88. }
  89.  
  90. int index(Node *n) noexcept {
  91.     Node *l = n->l;
  92.     return l ? l->size + 1 : 1;
  93. }
  94.  
  95. pair<Node *, Node *> split(Node *t, int i) noexcept {
  96.     if (!t) {
  97.         return {nullptr, nullptr};
  98.     } else if (index(t) < i) {
  99.         auto[a, b] = split(t->r, i - index(t));
  100.         return {t->withRight(a), b};
  101.     } else {
  102.         auto[a, b] = split(t->l, i);
  103.         return {a, t->withLeft(b)};
  104.     }
  105. }
  106.  
  107. tuple<Node *, Node *, Node *> split(Node *t, int l, int r) noexcept {
  108.     auto[a, T] = split(t, l);
  109.     auto[b, c] = split(T, r - s(a));
  110.     return {a, b, c};
  111. }
  112.  
  113. Node *merge(Node *l, Node *r) noexcept {
  114.     if (!l || !r) return l ? l : r;
  115.     else if (nextRand24() % (l->size + r->size) > r->size) {
  116.         return l->mutateRight(merge(l->r, r));
  117.     } else {
  118.         return r->mutateLeft(merge(l, r->l));
  119.     }
  120. }
  121.  
  122. Node *merge(Node *a, Node *b, Node *c) noexcept {
  123.     return merge(merge(a, b), c);
  124. }
  125.  
  126. void traversePrint(Node *t) {
  127.     if(!t) return;
  128.     traversePrint(t->l);
  129.     writeInt(t->x, ' ');
  130.     traversePrint(t->r);
  131. }
  132.  
  133. void print(Node *t, int l, int r) noexcept {
  134.     if (!t || r <= l || r <= 0) return;
  135.     auto[A, B, C] = split(t, l, r);
  136.     traversePrint(B);
  137. }
  138.  
  139. size_t sum(Node *t, int l, int r) noexcept {
  140.     if (!t || r <= l || r <= 0) return 0;
  141.     if (l <= 1 && r > t->size) return t->sum;
  142.     auto[A, B, C] = split(t, l, r);
  143.     return ss(B);
  144. }
  145.  
  146.  
  147. Node *build(const vector<int>& v, int l, int r) {
  148.     if(r <= l) return nullptr;
  149.     if(l == r - 1) return new Node(v[l]);
  150.     int m = (l + r) / 2;
  151.     Node *nn = new Node(v[m]);
  152.     nn->l = build(v, l, m);
  153.     nn->r = build(v, m + 1, r);
  154.     nn->recalc();
  155.     return nn;
  156. }
  157.  
  158. void traverse(Node *t, vector<int>& to) {
  159.     if(!t) return;
  160.     traverse(t->l, to);
  161.     to.push_back(t->x);
  162.     traverse(t->r, to);
  163. }
  164.  
  165. int main() {
  166.     int n = readInt();
  167.     auto X = readInt<size_t>(), A = readInt<size_t>(), B = readInt<size_t>(), M = readInt<size_t>();
  168.     Node *root;
  169.     {
  170.         vector<int> xs;
  171.         xs.reserve(n);
  172.         xs.push_back(X);
  173.         for (int i = 1; i < n; ++i) {
  174.             X = (A * X + B);
  175.             if (X > M) X %= M;
  176.             xs.push_back(X);
  177.         }
  178.         root = build(xs, 0, n);
  179.         assert(root->depth < 30);
  180.     }
  181.     constexpr int Kc = 10000;
  182.     int K = Kc;
  183.     int k = readInt();
  184.     for (int j = 0; j < k; ++j) {
  185.         if(--K == 0) {
  186.             K = Kc;
  187.             vector<int> data;
  188.             data.reserve(n);
  189.             traverse(root, data);
  190.             allocator_pos = 0;
  191.             root = build(data, 0, n);
  192.         }
  193.         int c = readChar();
  194.         readChar();
  195.         readChar();
  196.         switch (c) {
  197.             case 'o': { //out
  198.                 auto l = readInt<size_t>(), r = readInt<size_t>();
  199.                 print(root, l, r + 1);
  200.                 writeChar('\n');
  201.                 break;
  202.             }
  203.             case 'c': { //cpy
  204.                 auto a = readInt<size_t>(), b = readInt<size_t>(), l = readInt<size_t>();
  205.                 auto[A1, B1, C1] = split(root, a, a + l);
  206.                 auto[A2, B2, C2] = split(root, b, b + l);
  207.                 root = merge(A2, B1, C2);
  208.                 break;
  209.             }
  210.             case 's': { //sum
  211.                 auto l = readInt<size_t>(), r = readInt<size_t>() + 1;
  212.                 writeInt(sum(root, l, r), '\n');
  213.                 break;
  214.             }
  215.             default:
  216.                 assert(false);
  217.         }
  218.     }
  219.     return 0;
  220. }
Advertisement
Add Comment
Please, Sign In to add comment