[Toph] Taju Kage Bunshin No Jutsu

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Taju Kage Bunshin No Jutsu
Source            : Toph.CO
Category          : Data Structure
Algorithm         : Persistent Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 4e5 + 5;  
static const int Max = 2e7 + 5;  
  
struct Node  
{  
      int st;  
      int lft, rgt;  
      Node(int st = 0, int lft = 0, int rgt = 0) : st(st), lft(lft), rgt(rgt) {}  
} Tree[Max];  
  
int version[maxn];  
int NODES;  
int N = 300000 + 5;  
  
int update(int root, int a, int b, int pos, int val)  
{  
      int newNode = ++NODES;  
      Tree[newNode] = Tree[root];  
      if (a == b)  
      {  
            Tree[newNode].st += val;  
            return newNode;  
      }  
      int mid = (a + b) >> 1;  
      if (pos <= mid) Tree[newNode].lft = update(Tree[newNode].lft, a, mid, pos, val);  
      else Tree[newNode].rgt = update(Tree[newNode].rgt, mid + 1, b, pos, val);  
      Tree[newNode].st = Tree[ Tree[newNode].lft ].st + Tree[ Tree[newNode].rgt ].st;  
      return newNode;  
}  
  
int query(int proot, int root, int a, int b, int k)  
{  
      if (a == b) return a;  
      int mid = a + b >> 1;  
      int sizeLeftChild = Tree[ Tree[root].lft ].st - Tree[ Tree[proot].lft ].st;  
      if (k <= sizeLeftChild) return query(Tree[proot].lft, Tree[root].lft, a, mid, k);  
      else return query(Tree[proot].rgt, Tree[root].rgt, mid + 1, b, k - sizeLeftChild);  
}  
  
void init()  
{  
      NODES = 0;  
      version[0] = 0;  
      for (int i = 0; i < maxn; i++) Tree[i] = Node();  
}  
  
struct Query  
{  
      int type;  
      int v;  
      int l, r, k;  
      Query(int type = 0, int v = 0, int l = 0, int r = 0, int k = 0)  
            : type(type)  
            , v(v)  
            , l(l)  
            , r(r)  
            , k(k) {}  
};  
  
vector <Query> queries;  
vector <int> vec;  
int arr[maxn];  
map <int, int> mapper, rmapper;  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n;  
      cin >> n;  
      for (int i = 1; i <= n; i++)  
      {  
            cin >> arr[i];  
            vec.emplace_back(arr[i]);  
      }  
      int q;  
      cin >> q;  
      for (int i = 1; i <= q; i++)  
      {  
            int type;  
            cin >> type;  
            if (type == 1)  
            {  
                  int v;  
                  cin >> v;  
                  queries.emplace_back(type, v);  
                  vec.emplace_back(v);  
            }  
            else if (type == 2)  
            {  
                  queries.emplace_back(type);  
            }  
            else  
            {  
                  int l, r, k;  
                  cin >> l >> r >> k;  
                  queries.emplace_back(type, 0, l, r, k);  
            }  
      }  
      sort(vec.begin(), vec.end());  
      int ptr = 0;  
      for (int x : vec)  
      {  
            if (mapper.find(x) == mapper.end())  
            {  
                  mapper[x] = ++ptr;  
                  rmapper[ptr] = x;  
            }  
      }  
      init();  
      for (int i = 1; i <= n; i++)  
      {  
            arr[i] = mapper[ arr[i] ];  
            version[i] = update(version[i-1], 1, N, arr[i], 1);  
      }  
      int lastVersion = n;  
      for (Query &it : queries)  
      {  
            if (it.type == 1)  
            {  
                  it.v = mapper[it.v];  
                  int newVersion = lastVersion + 1;  
                  version[newVersion] = update(version[lastVersion], 1, N, it.v, 1);  
                  lastVersion = newVersion;  
            }  
            else if (it.type == 2)  
            {  
                  --lastVersion;  
            }  
            else  
            {  
                  int l = it.l;  
                  int r = it.r;  
                  int k = it.k;  
                  k = (r - l + 1) - k + 1;  
                  int kth = query(version[l-1], version[r], 1, N, k);  
                  cout << rmapper[kth] << endl;  
            }  
      }  
}