# Cod sursa(job #386533)

Utilizator Data 25 ianuarie 2010 03:23:46 Secv8 40 cpp done Arhiva de probleme 5.29 kb
``````#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

class Treap {
public:
struct Node {
int key, val, prio, sum;
bool rev;
Node *left, *right;
Node() { key = val = prio = 0; rev = false; left = right = NULL; }
Node ( int K, int V, int P = -1, Node *L = NULL, Node *R = NULL, bool REV = false ) {
key = K; val = V; prio = P;
rev = REV;
left = L; right = R;
if (prio == -1)
prio = rand() % (INF-1) + 1;
}
};
private:
Node *root;
bool empty;

void rotateRight ( Node *node ) {
Node *newRight = new Node(node->key, node->val, node->prio, node->left->right, node->right);
Node *aux = node->left;
node->key = node->left->key;
node->val = node->left->val;
node->prio = node->left->prio;
node->left = node->left->left;
node->right = newRight;
delete aux;
}
void rotateLeft ( Node *node ) {
Node *newLeft = new Node(node->key, node->val, node->prio, node->left, node->right->left);
Node *aux = node->right;
node->key = node->right->key;
node->val = node->right->val;
node->prio = node->right->prio;
node->right = node->right->right;
node->left = newLeft;
delete aux;
}
void reverse ( Node *node ) {
if (node != NULL && node->rev) {
if (node->left != NULL) node->left->rev = !node->left->rev;
if (node->right != NULL) node->right->rev = !node->right->rev;
swap(node->left, node->right);
node->rev = false;
}
}
void lazyUpdate ( Node *node ) {
reverse(node);
if (node != NULL) reverse(node->left);
if (node != NULL) reverse(node->right);
}
void updateSum ( Node *cur ) {
cur->sum = (cur->left != NULL ? cur->left->sum : 0) + (cur->right != NULL ? cur->right->sum : 0) + 1;
}
public:
Node* getRoot() { return root; }
Node* rootIn ( Node *R ) {
root = R;
empty = (R == NULL);
return root;
}
Treap ( Node *R = NULL ) {
srand(unsigned(time(0)));
rootIn(R);
}
void dealloc ( Node *cur ) {
if (cur != NULL) {
dealloc(cur->left);
dealloc(cur->right);
delete cur;
}
}
~Treap() {
dealloc(root);
}

Node* search ( int pos ) { return search(pos, root); }
Node* search ( int pos, Node *cur ) {
lazyUpdate(cur);
if ((cur->left != NULL ? cur->left->sum : 0) + 1 == pos)
return cur;
if ((cur->left != NULL) && cur->left->sum + 1 >= pos)
return search(pos, cur->left); else
return search(pos - (cur->left == NULL ? 0 : cur->left->sum) - 1, cur->right);
}

Node* insert ( Node x ) { return insert(x, root); }
Node* insert ( Node x, Node *cur ) {
if (cur == NULL) {
cur = new Node(x);
cur->sum = 1;
if (empty) {
root = cur;
empty = false;
}
return cur;
}
lazyUpdate(cur);
if (cur->left != NULL && x.key <= cur->left->sum+1 || x.key <= 1) {
cur->left = insert(x, cur->left);
if (cur->prio < cur->left->prio)
rotateRight(cur);
} else {
x.key -= (cur->left != NULL ? cur->left->sum : 0) + 1;
cur->right = insert(x, cur->right);
if (cur->prio < cur->right->prio)
rotateLeft(cur);
}
return cur;
}

Node* erase ( Node *cur ) {
lazyUpdate(cur);
if (cur->left == NULL && cur->right == NULL) {
if (root == cur) rootIn(NULL);
delete cur;
return NULL;
}
if ((cur->left != NULL && cur->right != NULL && cur->left->prio > cur->right->prio) || cur->right == NULL) {
rotateRight(cur);
cur->right = erase(cur->right);
} else {
rotateLeft(cur);
cur->left = erase(cur->left);
}
return cur;
}

void split ( int key, Treap &T1, Treap &T2 ) {
insert(Node(key, 0, INF));
T1.rootIn(root->left);
T2.rootIn(root->right);
delete root;
rootIn(NULL);
}

Node* join ( Treap &T1, Treap &T2 ) {
Node *tmp = new Node(0,0,0, T1.getRoot(), T2.getRoot());
rootIn(tmp);
rootIn(erase(tmp));
T1.rootIn(NULL);
T2.rootIn(NULL);
return root;
}

Node* reverse ( int p1, int p2 ) {
Treap T1, T2, T3, T4;
split(p1, T1, T2);
T2.split(p2-p1+2, T3, T4);
T3.getRoot()->rev = true;
T2.join(T3,T4);
join(T1,T2);
return root;
}

Node* erase ( int p1, int p2 ) {
Treap T1, T2, T3, T4;
split(p1, T1, T2);
T2.split(p2-p1+2, T3, T4);
join(T1, T4);
return root;
}

void print( FILE* stream = stdout ) { print(root,stream); /*fprintf(stream,"\n");*/ }
void print ( Node *cur, FILE* stream ) {
lazyUpdate(cur);
if (cur != NULL) {
print(cur->left,stream);
fprintf(stream,"%d ",cur->val);
print(cur->right,stream);
}
}
};

int main() {
freopen("secv8.in","rt",stdin);
freopen("secv8.out","wt",stdout);

int n;
char op; int a,b;
Treap T;

scanf("%d %*d",&n);
for (int i = 0; i < n; ++i) {
scanf(" %c ",&op);
if (op == 'I') {
scanf("%d %d",&a,&b);
T.insert(Treap::Node(a,b));
} else
if (op == 'A') {
scanf("%d",&a);
Treap::Node *ans = T.search(a);
printf("%d\n",ans->val);
} else
if (op == 'R') {
scanf("%d %d",&a,&b);
T.reverse(a,b);
} else
if (op == 'D') {
scanf("%d %d",&a,&b);
T.erase(a,b);
}
//		fprintf(stderr,"%c %d %d: ",op,a,b);
//		T.print(stderr);
}
T.print();
return 0;
}
``````