# Cod sursa(job #2483333)

Utilizator Data 29 octombrie 2019 17:54:42 Secv8 100 cpp-64 done Arhiva de probleme 5.01 kb
``````#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#define INF 2000000000
using namespace std;
struct treap{
int key;
int pri;
int revers;
int nodes;
treap *st , *dr;

treap (int key,int pri,treap *st,treap *dr,int revers,int nodes){
this->key=key;
this->pri=pri;
this->st=st;
this->dr=dr;
this->revers = revers;
this->nodes = nodes;
}

};
treap *r , *nil,*rl,*rr,*ruseless,*rmid;

void update (treap *&n){ /// update valorilor din n
if (n!=nil)
n->nodes = n->st->nodes + 1 + n->dr->nodes;
}

void update_reverse (treap *&n){
if (n!=nil && n->revers){
n->st->revers = 1 - n->st->revers;
n->dr->revers = 1 - n->dr->revers;
n->revers = 0;
treap *aux = n->st;
n->st = n->dr;
n->dr = aux;
}
}

pair <treap* , treap*> split (treap *r , int position){
pair <treap* , treap*> p;
if (r == nil)
return make_pair(nil,nil);
update(r);
update_reverse(r);
if (r->st->nodes + 1 == position){ /// TO DO
p.first = r->st;
p.second = r;
p.second->st = nil;
update(p.second);
update_reverse(p.second);
return p;
}
else if (r->st->nodes+1 < position){
/// r + r->left clar apartine treapului left , r->right nu stiu
p = split (r->dr , position - r->st->nodes - 1);
r->dr = p.first;
p.first = r;
update(r);
update_reverse(r);
return p;
}
else {
/// r + r->right clar apartine treapului right , r->left nu stiu
p = split (r->st , position);
r->st = p.second;
p.second = r;
update(r);
update_reverse(r);
return p;
}
}

treap* join (treap *t1 , treap* t2){

if (t1 == nil)
return t2;
if (t2 == nil)
return t1;
update (t1);
update_reverse(t1);
update (t2);
update_reverse(t2);
if (t1->pri > t2->pri){ /// t1 trb sa fie deasupra lui t2
t1->dr = join (t1->dr , t2);
update(t1);
return t1;
}
else { /// t2 e deasupra lui t1
t2->st = join(t1 , t2->st);
update(t2);
return t2;
}

}

int cauta (treap *&r , int poz){
update(r);
update_reverse(r);
if (r->st->nodes + 1 == poz){
return r->key;
}
else{
if (r->st->nodes + 1 < poz)
return cauta (r->dr , poz - 1 - r->st->nodes);
return cauta (r->st , poz);
}

}

void inser (treap*&r , int key , int position , int pri){
pair <treap* , treap*> p;
// if (key == 1 && position == 2)
//   printf ("a");
if (r == nil){
r = new treap (key,pri,nil,nil,0,1);
return;
}
update(r); update_reverse(r);

if (r->pri <= pri){ /// nodul meu ar trb sa fie deasupra lui r

p = split (r , position);
r = new treap (key,pri,p.first,p.second,0,1);
update(r);
update_reverse(r);

}
else if (position <= r->st->nodes + 1) {
inser(r->st , key , position , pri);
}
else {
inser(r->dr , key , position - r->st->nodes - 1 , pri);
}
update(r); update_reverse(r);

}

int main()
{
FILE *fin = fopen ("secv8.in","r");
FILE *fout = fopen ("secv8.out","w");
int q,ok,x,y;
char c;
pair <treap* , treap*> p1 , p2;

//srand(time(0));

r = nil = new treap (0,0,NULL,NULL,0,0);

int elem = 0;

fscanf (fin,"%d%d\n",&q,&ok);
for (;q;q--){
c=fgetc(fin);
if (c == 'I'){
fscanf (fin,"%d%d\n",&y,&x);
elem++;
/// insert elem x poz y
inser (r,x,y,rand()%INF+1);
}
else if (c == 'A'){
fscanf (fin,"%d\n",&x);
/// access elem poz x
fprintf (fout,"%d\n",cauta (r,x));

/* for (int i=1;i<=elem;i++)
printf ("%d ",cauta (r,i));
printf ("\n"); */

}
else if (c == 'R'){
fscanf (fin,"%d%d\n",&x,&y);
/// reverse x .. y
p1 = split (r , y+1);
rmid = p1.first;
rr = p1.second;
p2 = split (rmid , x);
rl = p2.first;
ruseless = p2.second;
ruseless->revers = 1;
rmid = join (rl,ruseless);
r = join (rmid,rr);
}
else{
fscanf (fin,"%d%d\n",&x,&y);
/// delete x .. y
p1 = split (r , y+1);
rmid = p1.first;
rr = p1.second;
p2 = split (rmid , x);
rl = p2.first;
ruseless = p2.second;
r = join (rl,rr);
elem = elem - (y - x + 1);
//for (int i=1;i<=elem;i++)
//  printf ("%d ",cauta (r,i));
}
}
for (int i = 1 ; i <= elem ; i ++)
fprintf (fout,"%d ",cauta(r,i));
return 0;
}
``````