Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "optimization.h"
- int allocator_pos = 0;
- char allocator_memory[1000000000];
- void *operator new(size_t n) {
- char *res = allocator_memory + allocator_pos;
- allocator_pos += n;
- return (void *) res;
- }
- void operator delete(void *) noexcept {}
- #include <vector>
- using namespace std;
- long long U = 35345312, L = 512313;
- unsigned long long cur = 0;
- inline unsigned long long nextRand24() {
- cur = cur * U + L;
- return cur >> 8u;
- }
- struct Node;
- inline int s(Node *n) noexcept;
- inline size_t ss(Node *n) noexcept;
- struct Node {
- int x;
- Node *l, *r;
- int size = -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);
- }
- void recalc() noexcept {
- size = s(l) + s(r) + 1;
- sum = ss(l) + ss(r) + x;
- }
- void full_recalc() noexcept {
- if(l) l->full_recalc();
- if(r) r->full_recalc();
- recalc();
- }
- };
- inline int s(Node *n) noexcept {
- return n ? n->size : 0;
- }
- inline size_t ss(Node *n) noexcept {
- return n ? n->sum : 0;
- }
- inline 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)};
- }
- }
- Node *merge(Node *l, Node *r) noexcept {
- if (!l || !r) return l ? l : r;
- else if (nextRand24() * r->size < nextRand24() * l->size) {
- return l->withRight(merge(l->r, r));
- } else {
- return r->withLeft(merge(l, r->l));
- }
- }
- void print(Node *t, int l, int r) noexcept {
- if (!t || r <= l || r <= 0) return;
- int i = index(t);
- print(t->l, l, min(i, r));
- if (l <= i && i < r) writeInt(t->x, ' ');
- print(t->r, max(l - i, 0), r - i);
- }
- 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;
- int i = index(t);
- size_t s = 0;
- s += sum(t->l, l, r);
- if (l <= i && i < r) s += t->x;
- s += sum(t->r, max(l - i, 0), r - i);
- return s;
- }
- 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;
- }
- int main() {
- int n = readInt();
- size_t X = readInt<size_t>(), A = readInt<size_t>(), B = readInt<size_t>(), M = readInt<size_t>();
- 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);
- }
- Node *root = build(xs, 0, n);
- int k = readInt();
- for (int j = 0; j < k; ++j) {
- int c = readChar();
- readChar();
- readChar();
- switch (c) {
- case 'o': { //out
- int l = readInt(), r = readInt();
- print(root, l, r + 1);
- writeChar('\n');
- break;
- }
- case 'c': { //cpy
- int a = readInt(), b = readInt(), l = readInt();
- auto[A1, T1] = split(root, a);
- auto[B1, C1] = split(T1, a + l - s(A1));
- auto[A2, T2] = split(root, b);
- auto[B2, C2] = split(T2, b + l - s(A2));
- root = merge(merge(A2, B1), C2);
- break;
- }
- case 's': { //sum
- int l = readInt(), r = readInt() + 1;
- writeInt(sum(root, l, r), '\n');
- break;
- }
- default:
- assert(false);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement