Template for Treap

#include<bits/stdc++.h>
using namespace std;

struct Key
{
  int reliability, id;
  Key(int _id, int _reliability = 0): id(_id), reliability(_reliability) {}
  bool operator<(const Key & b) { return reliability > b.reliability || reliability == b.reliability && id < b.id; }
};

struct SecurityNode
{
  string code;
  Key key;
  int y, left, right, cnt;
  SecurityNode(): key(0) {}
};

const int MAX_CNT = 100000;
vector<bool> deleted(MAX_CNT + 1, false);
SecurityNode nodes[MAX_CNT + 1];
unordered_map<string, int> code_id;

int root_id = 0, last_used_id = 0;

int get_cnt(const int & node_id) // return cnt-field value or zero
{
  if(!node_id) return 0;
  return nodes[node_id].cnt;
}

void update_cnt(const int & node_id); // update cnt-field value for node
pair<int, int> split(const int & node_id, Key & key); // return two treaps
int & merge(int & noed1, int & node2); // merge two treaps and return id of result treap

void insert(Key key, const string & code); // insert into treap
void erase(Key key); // erase node with key

// [0 ... n)
int get_k(const int & node_id, const int & k) // return node_id for element in k position
{
  if (!node_id) return 0;
  int left_cnt = get_cnt(nodes[node_id].left);
  if (k < left_cnt) return get_k(nodes[node_id].left, k);
  if (k == left_cnt || !nodes[node_id].right) return node_id;
  return get_k(nodes[node_id].right, k - (left_cnt + 1));
}

int main()
{
  // TODO
}