Pasted

 
 
 
#include "optimization.h"
 
int allocator_pos = 0;
char allocator_memory[1000000000];
#include <tuple>
#include <vector>
#include <random>
 
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<Node *, Node *> 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<Node *, Node *, Node *> 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<int>& 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<int>& 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<size_t>(), A = readInt<size_t>(), B = readInt<size_t>(), M = readInt<size_t>();
    Node *root;
    {
        vector<int> 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<int> 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<size_t>(), r = readInt<size_t>();
                print(root, l, r + 1);
                writeChar('\n');
                break;
            }
            case 'c': { //cpy
                auto a = readInt<size_t>(), b = readInt<size_t>(), l = readInt<size_t>();
                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<size_t>(), r = readInt<size_t>() + 1;
                writeInt(sum(root, l, r), '\n');
                break;
            }
            default:
                assert(false);
        }
    }
    return 0;
}