Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- mt19937 rnd((long long)(new char));
- ifstream fin("secv8.in");
- ofstream fout("secv8.out");
- typedef struct Treap * Arbore;
- Arbore NIL;
- void Join();
- struct Treap {
- bool flip;
- int val;
- int nl;
- long long prio;
- Arbore st;
- Arbore dr;
- Treap(int val = 0) : flip(0), val(val), nl(1), prio(rnd()), st(NIL), dr(NIL) { }
- void propaga() {
- if (!flip)
- return;
- swap(st, dr);
- st->flip ^= 1;
- dr->flip ^= 1;
- }
- void recalc() {
- nl = st->nl + dr->nl;
- }
- void reverse_() {///nush daca o sa o folosesec dar sa fie acolo
- flip ^= 1;
- }
- void Split(Arbore &first, int cati, Arbore &second) {
- if (this == NIL) {
- assert(cati == 0);
- first = NIL;
- second = NIL;
- return;
- }
- propaga();
- if (cati > st->nl) {
- first = this;
- dr->Split(first->dr, cati - st->nl - 1, second);
- first->recalc();
- }
- else {
- second = this;
- st->Split(first, cati, second->st);
- second->recalc();
- }
- }
- void Insert(int poz, int val) {
- Arbore first, second, Elm = new Treap(val), aux;
- Split(first, poz - 1, second);
- Join(first, Elm, aux);
- Join(aux, second, this);
- }
- int Access(int poz) {
- assert(poz <= nl);
- propaga();
- Arbore first, _second, elm, second;
- Split(first, poz - 1, _second);
- _second->Split(elm, 1, second);
- int val(elm->val);
- Join(elm, second, _second);
- Join(first, _second, this);
- return val;
- }
- void Reverse(int l, int r) {
- Arbore left, middle, right, aux;
- Split(left, l - 1, aux);
- aux->Split(middle, r - l + 1, right);
- middle->reverse_();
- Join(middle, right, aux);
- Join(left, aux, this);
- }
- void Delete(int l, int r) {
- Arbore left, middle, right, aux;
- Split(left, l - 1, aux);
- aux->Split(middle, r - l + 1, right);
- Join(left, right, this);
- }
- };
- int main()
- {
- ///initializam NIL
- NIL->flip = 0;
- NIL->val = 0;
- NIL->nl = 0;
- NIL->prio = 0;
- NIL->st = nullptr;
- NIL->dr = nullptr;
- Arbore v = NIL;
- int q, a, b;
- char ch;
- bool uselesspentrucasuntpreaboss;
- fin >> q >> uselesspentrucasuntpreaboss;
- while (q--) {
- fin >> ch;
- if (ch == 'I') {
- fin >> a >> b;
- v->Insert(a, b);
- }
- else if (ch == 'A') {
- fin >> a;
- fout << v->Access(a) << '\n';
- }
- else if (ch == 'R') {
- fin >> a >> b;
- v->Reverse(a, b);
- }
- else {///if (ch == 'D)
- fin >> a >> b;
- v->Delete(a, b);
- }
- }
- return 0;
- }
- void Join(Arbore &first, Arbore &second, Arbore &ans) {
- first->propaga();
- second->propaga();
- if (first == NIL) {
- ans = second;
- return;
- }
- if (second == NIL) {
- ans = first;
- return;
- }
- if (first->prio > second->prio) {
- ans = first;
- Join(first->dr, second, ans->dr);
- ans->recalc();
- }
- else {
- ans = second;
- Join(first, second->st, ans->st);
- ans->recalc();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement