Lesson5

#include <iostream>
#include <random>

using namespace std;

struct TreapNode {
  int Data;
  int Priority = rand();
  TreapNode* Left = nullptr;
  TreapNode* Right = nullptr;
  int Count = 1;
  explicit TreapNode(int data) : Data(data) {}
};

int Count(TreapNode* node) { return node ? node->Count : 0; }
void Update(TreapNode* node) { node->Count = 1 + Count(node->Left) + Count(node->Right); }

pair<TreapNode*, TreapNode*> Split(TreapNode* node, int count) {
  if (!node) return {nullptr, nullptr};
  if (Count(node->Left) >= count) {
    auto [t1, t2] = Split(node->Left, count);
    node->Left = t2;
    Update(node);
    return {t1, node};
  } else {
    auto [t1, t2] = Split(node->Right, count - 1 - Count(node->Left));
    node->Right = t1;
    Update(node);
    return {node, t2};
  }
}

TreapNode* Merge(TreapNode* t1, TreapNode* t2) {
  if (!t1 || !t2) return t1 ? t1 : t2;
  if (t1->Priority > t2->Priority) {
    t1->Right = Merge(t1->Right, t2);
    Update(t1);
    return t1;
  } else {
    t2->Left = Merge(t1, t2->Left);
    Update(t2);
    return t2;
  }
}

void Insert(TreapNode*& root, int data, int pos) {
  auto [t1, t2] = Split(root, pos);
  TreapNode* node = new TreapNode(data);
  root = Merge(Merge(t1, node), t2);
}

void Print(TreapNode* node, string prefix = "") {
  if (node == nullptr) return;
  Print(node->Right, prefix + "  ");
  cout << prefix << node->Data << "\n";
  Print(node->Left, prefix + "  ");
}

int main() {
  srand(24);
  TreapNode* root = nullptr;
  Insert(root, 28, 0);
  Print(root);
  cout << "-----\n";
  Insert(root, 43, 1);
  Print(root);
  cout << "-----\n";
  Insert(root, 12, 0);
  Print(root);
  cout << "-----\n";
  Insert(root, 30, 2);
  Print(root);
  cout << "-----\n";
  Insert(root, 50, 4);
  Print(root);
  return 0;
}