#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const char iname[] = "secv.in";
const char oname[] = "secv.out";
class Treap {
private:
class Node {
public:
// cheia
int number;
// prioritatea, numarul descendentilor, variabila care indica daca fii nodului trebuie inversati
int priority, desc, reverse;
// fiul stang, fiul drept
Node *left, *right;
Node(const int p_number, const int p_priority) : number(p_number), priority(p_priority), desc(1), reverse(0), left(0), right(0) {}
Node(Node *p_left, Node *p_right) : left(p_left), right(p_right), number(0), desc(1 + (p_left ? p_left->desc : 0) + (p_right ? p_right->desc : 0)), reverse(0) {}
};
// Operatiile pe Treap
void get_desc(Node* ); // O(1)
void rotate_left(Node* & ); // O(1)
void rotate_right(Node* & ); // O(1)
void balance(Node* & ); // O(1)
void insert(Node* &, const int, const int, const int); // O(log N)
void erase(Node* &); // O(log N)
Node* search(Node* &, const int); // O(log N)
void update(Node* &); // O(1)
void walk(Node*, vector <int>& ); // O(N)
// Radacina Treapului
Node *R;
public:
Treap() : R(0) { // O(1)
srand(unsigned(time(0)));
}
/* Insereaza in Treap cheia number pe pozitia k. Complexitate: O(log N) */
void insert(const int k, const int number) {
insert(R, k - 1, number, rand() + 1);
}
/* Schimba ordinea cheilor din intervalul [i, j]. Complexitate: O(log N) */
void split(const int i, const int j) {
/* Ts: subarborele ce va contine cheile de pe pozitiile 1, 2,.., i-1
T: subarborele ce va contine cheile de pe pozitiile i, i+1, .., j
Tr: subarborele ce va contine cheile de pe pozitiile j+1, .., n
*/
Node *Ts, *T, *Tr;
/* Inserez un nod cu prioritate maxima, 0, dupa al i-1 ulea element.
Avand prioritate maxima va ajunge radacina arborelui. Fiul stang va fi Ts. */
insert(R, i - 1, 0, 0);
/* Se aplica acelasi lucru pentru subarborele ce contine elementele de pe pozitiile i, i+1, .., n */
insert(R->right, j - (i - 1), 0, 0);
Ts = R->left, T = R->right->left, Tr = R->right->right;
/* Intervalul [i, j] este rotit */
T->reverse ^= 1;
/* Sterg nodurile cu prioritate maxima care au impartit arborele */
delete R->right, delete R;
/* Unesc cei trei arbori intr-un Treap cu radacina in R */
R = new Node(Ts, T);
erase(R);
T = R, R = new Node(T, Tr);
erase(R);
}
void erase(const int i, const int j) {
Node *Ts, *T, *Tr;
insert(R, i - 1, 0, 0);
insert(R->right, j - (i - 1), 0, 0);
Ts = R->left, T = R->right->left, Tr = R->right->right;
delete R->right, delete R;
R = new Node(Ts, Tr);
erase(R);
}
// Intoarce cheia de pe pozitia k
int search(const int k) {
Node *n = search(R, k);
return n->number;
}
// Parcurge Treapul in inordine si aseaza elementele in vect pentru afisare
void walk(vector <int>& vect) { walk(R, vect); }
// Sterge Treapul din memorie
friend void erase_all(Node* &);
~Treap();
};
void Treap::walk(Node* n, vector <int>& vect) {
if (n) {
update(n), update(n->left), update(n->right);
walk(n->left, vect), vect.push_back(n->number), walk(n->right, vect);
}
}
void Treap::get_desc(Node* n) { n->desc = (n->left ? n->left->desc : 0) + (n->right ? n->right->desc : 0) + 1; }
void Treap::rotate_left(Node* &n) {
Node *m = n->left; n->left = m->right; m->right = n;
get_desc(n), get_desc(m), n = m;
}
void Treap::rotate_right(Node* &n) {
Node *m = n->right; n->right = m->left; m->left = n;
get_desc(n), get_desc(m), n = m;
}
void Treap::balance(Node* &n) {
if (n->left && n->left->priority < n->priority)
rotate_left(n);
else if (n->right && n->right->priority < n->priority)
rotate_right(n);
else
get_desc(n);
}
void Treap::insert(Node* &n, const int k, const int number, const int priority) {
if (n == 0)
n = new Node(number, priority);
else {
update(n), update(n->left), update(n->right);
if (k <= (n->left ? n->left->desc : 0))
insert(n->left, k, number, priority);
else
insert(n->right, k - (1 + (n->left ? n->left->desc : 0)), number, priority);
balance(n);
}
}
void Treap::erase(Node* &n) {
if (!n->left && !n->right)
delete n, n = 0;
else {
update(n), update(n->left), update(n->right);
if (n->left && n->right)
(n->left->priority < n->right->priority) ? (rotate_left(n), erase(n->right)) : (rotate_right(n), erase(n->left));
else
(n->left) ? (rotate_left(n), erase(n->right)) : (rotate_right(n), erase(n->left));
get_desc(n);
}
}
Treap::Node* Treap::search(Node* &n, const int k) {
update(n), update(n->left), update(n->right);
if ((n->left ? n->left->desc : 0) + 1 == k)
return n;
if (k <= (n->left ? n->left->desc : 0))
return search(n->left, k);
return search(n->right, k - (1 + (n->left ? n->left->desc : 0)));
}
void Treap::update(Node* &n) {
if (!n) return ;
if (n->left)
n->left->reverse ^= n->reverse;
if (n->right)
n->right->reverse ^= n->reverse;
if (n->reverse) {
Node *m = n->left; n->left = n->right; n->right = m;
n->reverse ^= 1;
}
}
void erase_all(Treap::Node* &n) {
if (n)
erase_all(n->left), erase_all(n->right), delete n, n = 0;
}
Treap::~Treap() { erase_all(R); }
int main(int argc, char* argv[]) {
ifstream in(iname);
ofstream out(oname);
Treap T;
char ch; int i, j, x; vector <int> vect;
/* Liniile din fisierul de intrare sunt de forma:
I i x (insereaza cheia x pe pozitia i)
R i j (schimba ordinea cheilor din intervalul [i, j])
A i (acceseaza cheia de pe pozitia i)
*/
while (in >> ch) {
if (ch == 'I')
in >> i >> x, T.insert(i, x);
else if (ch == 'R')
in >> i >> j, T.split(i, j);
else if (ch == 'A')
in >> i, out << T.search(i) <<"\n";
else if (ch == 'D') {
in >> i >> j;
for (int step = 0; step < j-i+1; ++ step)
T.erase(i, i);
}
}
T.walk(vect);
for (i = 0; i < (int)vect.size(); ++ i)
out << vect[i] <<" ";
in.close(), out.close();
return 0;
}