[Gym] 100155 – B. No Name

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 100155 – B. No Name
Source            : Codeforces Gym
Category          : Data Structure
Algorithm         : Implicit Treap
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define FI       freopen("in.txt", "r", stdin)
#define FO       freopen("out.txt", "w", stdout)
#define FAST     ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
 
static const int maxn = 2e5 + 5;
static const int logn = 18;
 
struct node
{
      char ch;
      int priority, sze;
      node *lft, *rgt;
      node(char ch)
      {
            this->ch = ch;
            this->priority = rand();
            this->sze = 1;
            this->lft = this->rgt = 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->lft) + 1 + sz(t->rgt);
}
 
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 = nullptr);
      int curr = sz(t->lft) + add;
      if (curr <= pos) Split(t->rgt, t->rgt, r, pos, curr+1), l = t;
      else Split(t->lft, l, t->lft, pos, add), r = t;
      updateSize(t);
}
 
inline void Merge(pnode &t, pnode l, pnode r)
{
      if (!l || !r) t = l ? l : r;
      else if (l->priority < r->priority) Merge(r->lft, l, r->lft), t = r;
      else Merge(l->rgt, l->rgt, 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 char kth(pnode t, int k) // k must be start from 1
{
      if (!t) return '?';
      int cur = sz(t->lft) + 1;
      if (cur == k) return t->ch;
      else if (cur < k) return kth(t->rgt, k - cur);
      else return kth(t->lft, k);
}
 
int main()
{
      string s;
      cin >> s;
      int len = s.size();
      pnode treap = nullptr;
      for (int i = 0; i < len; i++) Insert(treap, new node(s[i]), i);
      string type;
      while (cin >> type)
      {
            if (type[0] == 'E') break;
            if (type[0] == 'I')
            {
                  cin >> s;
                  int pos; cin >> pos;
                  for (int i = pos, j = 0; j < s.size(); j++, i++) Insert(treap, new node(s[j]), i);
            }
            else
            {
                  int st, ed;
                  cin >> st >> ed;
                  for (int k = st; k <= ed; k++) cout << kth(treap, k+1);
                  cout << endl;
            }
      }
}