# Cod sursa(job #2381231)

Utilizator Data 16 martie 2019 12:23:21 Secv8 25 cpp-64 done Arhiva de probleme 2.84 kb
``````#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

mt19937 rng(100);

struct node {
node *l, *r;
int val, pr, sz, rev;
node(int x = 0) : l(0), r(0), val(x), pr(rng()), sz(1), rev(0) {}
} *root, *lft, *rgt, *mmid;

typedef node* pnode;

void reset() {
lft = rgt = mmid = new node();
//lft = rgt = mmid = 0;
}

int sz(pnode v) {
return v ? v -> sz : 0;
}
void pull(pnode &v) {
if (v) v -> sz = sz(v -> l) + sz(v -> r) + 1;
}
void rev(pnode &v) {
if (v) v -> rev ^= 1;
}
void push(pnode v) {
if (v && v -> rev) {
v -> rev = 0;
swap(v -> l, v -> r);
rev(v -> l), rev(v -> r);
}
}

void merge(pnode &v, pnode l, pnode r) {
push(l), push(r);
if (!l || !r) {
v = l ? l : r;
} else if (l -> pr > r -> pr) {
merge(l -> r, l -> r, r);
v = l;
} else {
merge(r -> l, l, r -> l);
v = r;
}
pull(v);
}

void split(pnode v, pnode &l, pnode &r, int key) {
if (!v) return void(l = r = 0);
push(v);
if (key <= sz(v -> l)) {
split(v -> l, l, v -> l, key);
r = v;
} else {
split(v -> r, v -> r, r, key - sz(v -> l) - 1);
l = v;
}
pull(v);
}

void insert(int pos, int val) {
reset();
split(root, lft, rgt, pos - 1);
mmid -> val = val;
merge(root, lft, mmid);
merge(root, root, rgt);
}
void erase(int i, int j) {
reset();
split(root, lft, rgt, i - 1);
split(rgt, mmid, rgt, j - i + 1);
merge(root, lft, rgt);
}

void reverse(int i, int j) {
reset();
split(root, lft, rgt, i - 1);
split(root, mmid, rgt, j - i + 1);
rev(mmid);
merge(root, lft, mmid);
merge(root, root, rgt);
}

int get(int i) {
reset();
split(root, lft, rgt, i - 1);
split(rgt, mmid, rgt, 1);
int res = mmid -> val;
merge(root, lft, mmid);
merge(root, root, rgt);
return res;
}
int main() {
freopen("secv8.in", "r", stdin);
freopen("secv8.out", "w", stdout);
ios_base :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int q, x, y; char c;
cin >> q >> x;
cin >> c >> x >> y;
root = new node(y); q--;
int n = 1;
while (q --) {
cin >> c;
if (c == 'I') {
cin >> x >> y;
n++, insert(x, y);
} else if (c == 'A') {
cin >> x;
cout << get(x) << endl; //cout << flush;
} else if (c == 'R') {
cin >> x >> y;
reverse(x, y);
} else if (c == 'D') {
cin >> x >> y;
n -= y - x + 1, erase(x, y);
}
}
for (int i = 1; i <= n; i++) {
cout << get(i) << " ";
}
cout << endl;
return 0;
}
``````