Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment