#include "optimization.h" int allocator_pos = 0; char allocator_memory[1000000000]; #include #include #include using namespace std; int U = 4321, L = 54321; unsigned int cur = 0; std::mt19937 gen(234); inline size_t nextRand24() { // cur = cur * U + L; // return cur >> 8u; return gen(); } struct Node; int s(Node *n) noexcept; size_t ss(Node *n) noexcept; struct Node { int x; Node *l, *r; int size = -1; int depth = -1; size_t sum = -1; Node(size_t x, Node *l = nullptr, Node *r = nullptr) : x(x), l(l), r(r) { recalc(); } Node *withLeft(Node *nl) noexcept { return new Node(x, nl, r); } Node *withRight(Node *nr) noexcept { return new Node(x, l, nr); } Node *mutateLeft(Node *nl) { l = nl; recalc(); return this; } Node *mutateRight(Node *nr) { r = nr; recalc(); return this; } void recalc() noexcept { size = s(l) + s(r) + 1; sum = ss(l) + ss(r) + x; depth = max(l ? l->depth : 0, r ? r->depth : 0) + 1; } void full_recalc() noexcept { if(l) l->full_recalc(); if(r) r->full_recalc(); recalc(); } void *operator new(size_t n) { char *res = allocator_memory + allocator_pos; allocator_pos += n; return (void *) res; } void operator delete(void *) noexcept {} }; int s(Node *n) noexcept { return n ? n->size : 0; } size_t ss(Node *n) noexcept { return n ? n->sum : 0; } int index(Node *n) noexcept { Node *l = n->l; return l ? l->size + 1 : 1; } pair split(Node *t, int i) noexcept { if (!t) { return {nullptr, nullptr}; } else if (index(t) < i) { auto[a, b] = split(t->r, i - index(t)); return {t->withRight(a), b}; } else { auto[a, b] = split(t->l, i); return {a, t->withLeft(b)}; } } tuple split(Node *t, int l, int r) noexcept { auto[a, T] = split(t, l); auto[b, c] = split(T, r - s(a)); return {a, b, c}; } Node *merge(Node *l, Node *r) noexcept { if (!l || !r) return l ? l : r; else if (nextRand24() % (l->size + r->size) > r->size) { return l->mutateRight(merge(l->r, r)); } else { return r->mutateLeft(merge(l, r->l)); } } Node *merge(Node *a, Node *b, Node *c) noexcept { return merge(merge(a, b), c); } void traversePrint(Node *t) { if(!t) return; traversePrint(t->l); writeInt(t->x, ' '); traversePrint(t->r); } void print(Node *t, int l, int r) noexcept { if (!t || r <= l || r <= 0) return; auto[A, B, C] = split(t, l, r); traversePrint(B); } size_t sum(Node *t, int l, int r) noexcept { if (!t || r <= l || r <= 0) return 0; if (l <= 1 && r > t->size) return t->sum; auto[A, B, C] = split(t, l, r); return ss(B); } Node *build(const vector& v, int l, int r) { if(r <= l) return nullptr; if(l == r - 1) return new Node(v[l]); int m = (l + r) / 2; Node *nn = new Node(v[m]); nn->l = build(v, l, m); nn->r = build(v, m + 1, r); nn->recalc(); return nn; } void traverse(Node *t, vector& to) { if(!t) return; traverse(t->l, to); to.push_back(t->x); traverse(t->r, to); } int main() { int n = readInt(); auto X = readInt(), A = readInt(), B = readInt(), M = readInt(); Node *root; { vector xs; xs.reserve(n); xs.push_back(X); for (int i = 1; i < n; ++i) { X = (A * X + B); if (X > M) X %= M; xs.push_back(X); } root = build(xs, 0, n); assert(root->depth < 30); } constexpr int Kc = 10000; int K = Kc; int k = readInt(); for (int j = 0; j < k; ++j) { if(--K == 0) { K = Kc; vector data; data.reserve(n); traverse(root, data); allocator_pos = 0; root = build(data, 0, n); } int c = readChar(); readChar(); readChar(); switch (c) { case 'o': { //out auto l = readInt(), r = readInt(); print(root, l, r + 1); writeChar('\n'); break; } case 'c': { //cpy auto a = readInt(), b = readInt(), l = readInt(); auto[A1, B1, C1] = split(root, a, a + l); auto[A2, B2, C2] = split(root, b, b + l); root = merge(A2, B1, C2); break; } case 's': { //sum auto l = readInt(), r = readInt() + 1; writeInt(sum(root, l, r), '\n'); break; } default: assert(false); } } return 0; }