Seminar13

#include <iostream>
#include <random>
#include <ctime>

// Стуктура узла декартового дерева по неявному ключу.
struct Node {
  int Data;
  int Priority;
  int Count = 1;
  Node* Left = nullptr;
  Node* Right = nullptr;

  explicit Node(int data): Data(data), Priority(rand()) {}
};

int Count(Node* node) {
  return node ? node->Count : 0;
}

std::pair<Node*, Node*> Split(Node* node, int k) {
  assert(k <= Count(node));
  if (k == 0) return {nullptr, node};
  if (k == Count(node)) return {node, nullptr};

  if (Count(node->Left) >= k) {
    auto [first, second] = Split(node->Left, k);
    node->Left = second;
    return {first, node};
  } else {
    auto [first, second] = Split(node->Right, k - Count(node->Left) - 1);
    node->Right = first;
    return {node, second};
  }
}

int main() {
  time_t sid = time(0);
  std::cout << sid << std::endl;
  srand(sid);
  Node* root = new Node(5);
  std::cout << "Hello, World!" << std::endl;
  return 0;
}