Treap

#include<bits/stdc++.h>
using namespace std;
const int MAX_CNT = 200001;
struct Node
{
  int key, y, cnt;
  int left, right;

  Node(int pkey = 0): key(pkey), y(0), left(0), right(0), cnt(1) {}
  void gen_y()
  {
    y = (rand() << 15) | rand();
  }
};

Node nodes[MAX_CNT + 1];
int used_nodes = 0;
int root_id = 0; // id of root node

int alloc_node()
{
  assert(used_nodes < MAX_CNT);
  used_nodes ++;
  return used_nodes;
}

int get_cnt(const int & node)
{
  if (!node) return 0;
  return nodes[node].cnt;
}

void update_cnt(const int & node)
{
  int left_cnt = get_cnt(nodes[node].left);
  int right_cnt = get_cnt(nodes[node].right);
  nodes[node].cnt = left_cnt + right_cnt + 1;
}

// root [k]: k = 1 .. n
int get_node(const int & node, int k)
{
  if (!node) return node;
  int left_k = get_cnt(nodes[node].left);
  if (k == left_k + 1) return node;
  if (k < left_k + 1)
    return get_node(nodes[node].left, k);
  return get_node(nodes[node].right, k - (left_k + 1));
}

// [1 .. k] | [k+1 .. n]
pair<int, int> split(const int & node, int k)
{
  if (!node) return {0, 0};
  int left_k = get_cnt(nodes[node].left);
  if (k <= left_k)
  {
    auto res = split(nodes[node].left, k);
    nodes[node].left = res.second;
    update_cnt(node);
    return {res.first, node};
  }
  else
  {
    auto res = split(nodes[node].right, k - (left_k + 1));
    nodes[node].right = res.first;
    update_cnt(node);
    return {node, res.second};
  }
}

int merge(const int & node1, const int & node2)
{
  if (!node1) return node2;
  if (!node2) return node1;
  if ( nodes[node1].y <= nodes[node2].y )
  { // node1 - root of result merge
    nodes[node1].right = merge(nodes[node1].right, node2);
    update_cnt(node1);
    return node1;
  }
  else
  {
    nodes[node2].left = merge(node1, nodes[node2].left);
    update_cnt(node2);
    return node2;
  }
}

// after k
void insert(const int & key, const int & k)
{
  if (k > get_cnt(root_id) + 1) return;
  auto res = split(root_id, k);
  int new_node = alloc_node();
  nodes[new_node].gen_y();
  nodes[new_node].key = key;
  nodes[new_node].cnt = 1;
  root_id = merge(merge(res.first, new_node), res.second);
}

void erase(const int & k)
{
  if (k > get_cnt(root_id)) return;
  auto res1 = split(root_id, k);
  auto res2 = split(res1.first, k-1);
  root_id = merge( res2.first, res1.second );
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  freopen("INPUT.TXT", "r", stdin);
}