# Cod sursa(job #2481580)

Utilizator Data 27 octombrie 2019 09:30:44 Secv8 25 cpp-64 done Arhiva de probleme 3.05 kb
``````#include <bits/stdc++.h>

using namespace std;

const int MOD = (1 << 30) - 1;

struct nod
{
int nr;
int pr;
int dim;
int flip;
nod *st, *dr;

nod(int _nr, int _pr, int _dim, int _flip) : nr(_nr), pr(_pr), dim(_dim), flip(_flip) {};
};

nod *nil = new nod{0, 0, 0, 0};

void upd(nod *n)
{
//cout << n << "\n";

if(n == nil)
return;

if(n -> flip == 1)
{
if(n -> st != nil)
n -> st -> flip ^= 1;
if(n -> dr != nil)
n -> dr -> flip ^= 1;
swap(n -> st, n -> dr);

n -> flip = 0;
}
}

nod* mfiu(nod *n, int care, nod *fiu)
{
//if(n == nil)
//  return nil;

upd(n);

(care == 0 ? n -> st : n -> dr) = fiu;
n -> dim = n -> st -> dim + n -> dr -> dim + 1;

return n;
}

nod* join(nod *a, nod *b)
{
upd(a);
upd(b);

if(a == nil)
return b;

if(b == nil)
return a;

if(a -> pr > b -> pr)
return mfiu(a, 1, join(a -> dr, b));

else
return mfiu(b, 0, join(a, b -> st));
}

pair <nod*, nod*> split(nod *n, int k)
{
upd(n);

if(n == nil)
return {nil, nil};

if(n -> st -> dim + 1 <= k)
{
auto tmp = split(n -> dr, k - n -> st -> dim - 1);
return {mfiu(n, 1, tmp.first), tmp.second};
}

auto tmp = split(n -> st, k);
return {tmp.first, mfiu(n, 0, tmp.second)};
}

ofstream g("secv8.out");

void doAfis(nod *n)
{
if(n == nil)
return;

doAfis(n -> st);
g << n -> nr << " ";
doAfis(n -> dr);
}

void ansQues()
{
ifstream f("secv8.in");

nil -> st = nil;
nil -> dr = nil;

//cout << nil << "\n";

int q, x;
f >> q >> x;
while(q > 0)
{
q --;

//cout << q << "\n";

int k, e;
char tip;
f >> tip;
if(tip == 'I')
{
f >> k >> e;
auto tmp = split(rad, k - 1);
nod *nou = new nod{e, (int)((1LL * rand() * rand()) & MOD), 1, 0};
nou -> st = nou -> dr = nil;
//cout << " DAM JOIN\n";
//cout << tmp.first << " " << tmp.second << "\n";
}

else
if(tip == 'A')
{
f >> k;
auto tmp = split(rad, k - 1);
auto tmp2 = split(tmp.second, 1);
g << tmp2.first -> nr << "\n";

}

else
{
int i, j;
f >> i >> j;
auto tmp2 = split(tmp.first, i - 1);

if(tip == 'D')
{
delete tmp2.second;
tmp2.second = nil;
}

if(tip == 'R')
tmp2.second -> flip ^= 1;

}

//g << "++\n";
}