Cod sursa(job #2382288)

Utilizator wthICMurad Eynizade wthIC Data 18 martie 2019 07:05:22
Problema Secv8 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#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 = r = NULL;
    }
};

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) {
    if (root)return root->sz;
    return 0;
}

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

void split(pnode root,int key,int cnt,pnode &l,pnode &r) {
    if (!root) {
        l = r = NULL;
        return;
    }
    relax(root);
    int sm = cnt + get(root->l);
    if (key <= sm)split(root->l , key , cnt , l , root->l) , r = root;
    else split(root->r , key , sm + 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 , 0 , 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;
    relax(root);
    split(root , le , 0 , t1 , t2);
    split(t2 , ri - le + 1 , 0, t2 , t3);
    t2->rev = 1;
    mrg(root , t1 , t2);
    mrg(root , root , t3);
}

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


int n , x , y;

char ty;

int main()
{
    FAST_READ;
    srand(1337);
    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;
}