# Cod sursa(job #2381351)

Utilizator Data 16 martie 2019 16:35:56 Secv8 85 cpp-64 done Arhiva de probleme 2.92 kb
``````/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define F first
#define S second

using namespace std;

struct node{
int prior , val , sz , rev;
node *l , *r;
node(int _val,int _prior):val(_val) , prior(_prior) , sz(1) , rev(0) , l(0) , r(0){}
};

typedef node* pnode;

void relax(pnode &root) {
if (!root)return;
if (!root->rev)return;
root->rev = 0;
swap(root->l , root->r);
if (root->l) root->l->rev ^= 1;
if (root->r) root->r->rev ^= 1;
}

void output(pnode root) {
if (!root)return;
relax(root);
output(root->l);
cout<<root->val<<" ";
output(root->r);
}

int get(pnode root) {
return root ? root->sz : 0;
}

void upd(pnode &root) {
if (!root)return;
root->sz = get(root->l) + get(root->r) + 1;
}

void split(pnode root,int key,pnode &l,pnode &r) {
if (!root) {
l = r = NULL;
return;
}
relax(root);
if (key <= get(root->l))split(root->l , key , l , root->l) , r = root;
else split(root->r , key - get(root->l) - 1 , root->r , r) , l = root;
upd(l);
upd(r);
}

void mrg(pnode &root,pnode l,pnode r) {
relax(l);
relax(r);
if (!l || !r) {
if (l)root = l;
else root = r;
return;
}
if (l->prior > r->prior)mrg(l->r,l->r,r) , root = l;
else mrg(r->l,l,r->l) , root = r;
upd(root);
}

int kth(pnode root,int in,int cnt) {
relax(root);
int sm = cnt + get(root->l);
if (sm == in)return root->val;
if (sm < in)return kth(root->r,in,sm + 1);
return kth(root->l,in,cnt);
}

pnode root;

void ins(int in,int val) {
pnode l , r , nw;
split(root , in , l , r);
nw = new node(val ,  ((rand() & 32767) << 15) | (rand() & 32767));
mrg(l , l , nw);
mrg(root , l , r);
}

void rev(int le,int ri) {
pnode t1 , t2 , t3;
split(root , le , t1 , t2);
split(t2 , ri - le + 1, t2 , t3);
t2->rev ^= 1;
mrg(root , t1 , t2);
mrg(root , root , t3);
}

void del(int le,int ri) {
pnode t1 , t2 , t3;
split(root , le , t1 , t2);
split(t2 , ri - le + 1, t2 , t3);
mrg(root , t1 , t3);
}

int n , x , y;

char ty;

int main()
{
srand(time(NULL));
freopen("secv8.in" , "r" , stdin);
freopen("secv8.out" , "w" , stdout);
cin>>n>>x;
while (n--) {
cin>>ty;
if (ty == 'I') {
cin>>x>>y;
x--;
ins(x , y);
}
else if (ty == 'R') {
cin>>x>>y;
x--; y--;
rev(x , y);
}
else if (ty == 'A') {
cin>>x;
x--;
cout<<kth(root , x , 0)<<endl;
}
else {
cin>>x>>y;
x--; y--;
del(x , y);
}
}
output(root);
cout<<endl;
}``````