[Codeforces] D. Yet Another Array Queries Problem

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Yet Another Array Queries Problem
Source            : Codeforces
Category          : Data Structure
Algorithm         : Implicit Treap
Verdict           : Accepted 

Operation : 1. Reverse a segment
            2. Shift / Rotate a segment 

#include <bits/stdc++.h>
 
using namespace std;
 
static const int maxn = 2e5 + 5;
 
struct node
{
       int cval, priority, sze;
       bool rev;
       node *left, *right;
       node(int v = 0)
       {
              this->cval = v;
              this->priority = rand();
              this->sze = 1;
              this->rev = 0;
              this->left = nullptr;
              this->right = nullptr;
       }
};
 
typedef node*     pnode;
 
inline int sz(pnode t)
{
       if (t) return t->sze;
       return 0;
}
 
inline void updateSize(pnode t)
{
       if (t) t->sze = sz(t->left) + 1 + sz(t->right);
}
 
inline void push(pnode t)
{
       if (t && t->rev)
       {
              t->rev = 0;
              swap(t->left, t->right);
              if (t->left) t->left->rev ^= 1;
              if (t->right) t->right->rev ^= 1;
       }
}
 
inline void Split(pnode t, pnode &l, pnode &r, int pos, int add = 0)
{
       // 'pos' goes to left subtree
       if (!t) return void(l = r = NULL);
       push(t);
       int curr = sz(t->left) + add;
       if (curr <= pos) Split(t->right, t->right, r, pos, curr+1), l = t;
       else Split(t->left, l, t->left, pos, add), r = t;
       updateSize(t);
}
 
inline void Merge(pnode &t, pnode l, pnode r)
{
       push(l);
       push(r);
       if (!l || !r) t = l ? l : r;
       else if (l->priority < r->priority) Merge(r->left, l, r->left), t = r;
       else Merge(l->right, l->right, r), t = l;
       updateSize(t);
}
 
inline void Insert(pnode &t, pnode newNode, int pos)
{
       pnode L, R;
       Split(t, L, R, pos-1);
       Merge(t, L, newNode);
       Merge(t, t, R);
}
 
inline pnode Reverse(pnode t, int l, int r) // void function gives RTE
{
       if (!t) return t;
       pnode L, mid, R;
       Split(t, L, mid, l-1);
       Split(mid, t, R, r-l);
       t->rev ^= 1;
       Merge(mid, L, t);
       Merge(t, mid, R);
       return t;
}
 
inline pnode shift(pnode t, int l, int r)
{
       if (!t) return t;
       pnode L, mid, R;
       Split(t, L, mid, l-1);
       Split(mid, t, R, r-l);
 
       pnode t1, t2;
       Split(t, t1, t2, r-l-1);
       Merge(t, t2, t1);
 
       Merge(mid, L, t);
       Merge(t, mid, R);
       return t;
}
 
inline void output(pnode t)
{
       if (!t) return;
       push(t);
       output(t->left);
       //cout << t->cval << " ";
       output(t->right);
}
 
inline int kth(pnode t, int k)
{
       if (!t) return 0;
       int cur = sz(t->left) + 1;
       if (cur == k) return t->cval;
       if (cur < k) return kth(t->right, k - cur);
       else return kth(t->left, k);
}
 
int n, q, m;
 
int main()
{
 
    //freopen("in.txt", "r", stdin);
 
    pnode treap = nullptr;
    scanf("%d %d %d", &n, &q, &m);
    for (int i = 0; i < n; i++)
    {
           int x;
           cin >> x;
           pnode t;
           Merge(t, treap, new node(x));
           treap = t;
 
           // Or we can use Insert Function for 0-indexed and 1-indexed
           // Insert(treap, new node(x), i);
    }
    while (q--)
    {
        int type, l, r;
        scanf("%d %d %d", &type, &l, &r);
        l--;
        r--;
        if (type == 2) treap = Reverse(treap, l, r);
        else treap = shift(treap, l, r);
    }
    output(treap);
    while (m--)
    {
           int k;
           cin >> k;
           cout << kth(treap, k) << " ";
    }
}