Language: C++

#include <iostream>
#include <algorithm>
#include <random>
#include <functional>
#include <array>
#include <iomanip>
#include <experimental/optional>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <random>
#include <functional>
#include <array>
#include <initializer_list>

namespace vectree { namespace detail { namespace treap {
{

template<class T>
class node
{
  T value_;
  node<T> *lch_, *rch_;
  double priority_;
  unsigned tree_size_;

  enum class side
  { left, right, none };

  static constexpr auto sibling(side s) noexcept
  { return s == side::right ? side::left : side::right; }

  explicit node(T v, double p)          noexcept
  : value_{v}, lch_{nullptr}, rch_{nullptr}, priority_{p}, tree_size_{1}
  {}

  static auto cut_link(node<T>* parent, side s) -> void;
  static auto set_least_priority(node<T>*& tree, node<T>*& parent, side last_side) -> node<T>*;
  static auto erase_node(node<T>* tree, node<T>* parent, side last_side) -> node<T>*;

public:

  using node_ptr = node<T>*;
  using node_ptr_reference = node_ptr&;
  using node_ptr_const_reference = node_ptr const&;

  ~node()
  {
    if (lch_) delete lch_;
    if (rch_) delete rch_;
  }


  constexpr auto const& priority() const noexcept { return priority_; }

  constexpr auto& value()               noexcept
  { return value_; }

  constexpr auto const& value()   const noexcept
  { return value_; }
  
  constexpr auto size()           const noexcept
  { return tree_size_; }

  constexpr auto expired_left()   const
  { return !lch_; }

  constexpr auto expired_right()  const
  { return !rch_; }

  constexpr auto expired_both()   const
  { return expired_left() && expired_right(); }

  auto left()               -> node_ptr_reference;
  auto left()        const  -> node_ptr_const_reference;
  auto right()              -> node_ptr_reference;
  auto right()       const  -> node_ptr_const_reference;
  auto child(side w)        -> node_ptr_reference;
  auto child(side w) const  -> node_ptr_const_reference;

  auto update_size()                                          -> void;
  static auto rotate(node_ptr tree, side right)               -> node_ptr;
  static auto insert(node_ptr tree, unsigned position, T val) -> node_ptr;
  static auto nth_element(node_ptr tree, unsigned position)   -> node_ptr;
  static auto erase(node_ptr tree, unsigned position) -> node_ptr;
  static auto erase(node_ptr tree, unsigned position, node_ptr parent, side direction) -> node_ptr;

  static auto predecessor(node_ptr t)                         -> node_ptr;
  static auto successor(node_ptr t)                           -> node_ptr;

  static auto create(T val)
  {
    static auto rand_priority_gen = std::bind(
      std::uniform_real_distribution<>{0.0, 1.0},
      std::default_random_engine{});
    return new node(val, rand_priority_gen());
  }

};
}}}

namespace vectree
{

template<class T>
class vectree
{
  using treap    = detail::treap::node<T>;
  using node_ptr = typename treap::node_ptr;

  node_ptr root {nullptr};

public:

  vectree() = default;

  ~vectree()
  {
    if (root) { delete root; }
  }

  auto size() const noexcept
  { return root ? root->size() : 0; }

  T operator[] (unsigned position) const { return treap::nth_element(root, position)->value(); }

  auto insert(unsigned position, T val)
    -> void
  {
    root = treap::insert(root, position, val);
  }

  auto push_back(T val)
    -> void
  {
    root = treap::insert(root, size(), val);
  }

  auto push_front(T val)
    -> void
  {
    root = treap::insert(root, 0, val);
  }

  auto erase(unsigned position)
    -> void
  {
    root = treap::erase(root, position, nullptr);
  }

  auto clear()
    -> void
  {
    if (root) delete root;
    root = nullptr;
  }
};

}


namespace vectree{ namespace detail {namespace treap {

template<class T>
auto node<T>::left()
  -> node<T>::node_ptr_reference
{ return lch_; }

template<class T>
auto node<T>::right()
  -> node<T>::node_ptr_reference
{ return rch_; }

template<class T>
auto node<T>::left() const
  -> node<T>::node_ptr_const_reference
{
  assert(!expired_left());
  return lch_;
}

template<class T>
auto node<T>::right() const
  -> node<T>::node_ptr_const_reference
{
  assert(!expired_right());
  return rch_;
}

template<class T>
auto node<T>::child(side s)
  -> node_ptr_reference
{ return s == side::left ? left() : right(); }

template<class T>
auto node<T>::child(side s) const
  -> node_ptr_const_reference
{ return s == side::left ? left() : right(); }

template<class T>
auto node<T>::update_size()
  -> void
{
  tree_size_ =
    1 + (expired_left()  ? 0 : left()->size())
      + (expired_right() ? 0 : right()->size());
}

template<class T>
auto node<T>::rotate(node<T>::node_ptr tree, side dir)
  -> node<T>::node_ptr
{
  auto const subtree = tree->child(node<T>::sibling(dir));
  tree->child(node<T>::sibling(dir)) = subtree->child(dir);
  subtree->child(dir) = tree;
  tree->update_size();
  subtree->update_size();
  return subtree;
}

template<class T>
auto node<T>::insert(node<T>::node_ptr tree, unsigned position, T val)
  -> node<T>::node_ptr
{
  if (!tree)
  {
    tree = node<T>::create(val);
    tree->update_size();
    return tree;
  }

  auto const left_size = tree->expired_left() ? 0 : tree->left()->size();
  auto const to_right = left_size < position;

  auto const next_tree = to_right ? tree->right() : tree->left();
  auto const subtree_pos = position - (to_right ? 1 + left_size : 0);
  auto const inserted_subtree = insert(next_tree, subtree_pos, val);

  (to_right ? tree->right() : tree->left()) = inserted_subtree;

  tree->update_size();

  if (tree->priority() < inserted_subtree->priority())
  {
    return rotate(tree, to_right ? side::left : side::right);
  }

  return tree;
}

template<class T>
auto node<T>::cut_link(node<T>::node_ptr parent, side s)
  -> void
{
  (s == side::left ? parent->left() : parent->right()) = nullptr;
}

template<class T>
auto node<T>::set_least_priority(node<T>::node_ptr& deletee, node<T>::node_ptr& parent, side last_side)
  -> node_ptr
{
  puts("start - set_least_priority()");

  node<T>::node_ptr ret {nullptr};

  while (true)
  {
    node<T>::node_ptr ntree {nullptr};
    if (deletee->expired_both())
    {
      puts("expired_both()");
      break;
    }
    else if (deletee->expired_left())
    {
      std::swap(deletee->value(), deletee->right()->value());
      ntree   = deletee;
      deletee = deletee->right();
    }
    else if (deletee->expired_right())
    {
      std::swap(deletee->value(), deletee->left()->value());
      ntree   = deletee;
      deletee = deletee->left();
    }
    else
    {
      auto right_up = deletee->left()->priority() < deletee->right()->priority();
      ntree = rotate(deletee, (last_side = (right_up ? side::left : side::right)));
      ntree->update_size();
    }

    if (!ret)
    {
      ret = ntree;
    }

    if (parent)
    {
      (last_side == side::right ? parent->left() : parent->right()) = ntree;
    }

    parent = ntree;
  }

  puts("end");

  return ret;
}

template<class T>
auto node<T>::erase_node(node<T>::node_ptr deletee, node<T>::node_ptr parent, side last_side)
  -> node_ptr
{
  // ??????????????°????????¨
  node<T>::node_ptr ret {set_least_priority(deletee, parent, last_side)};

  puts("start - cut_link");
  cut_link(parent, last_side);
  puts("end");

  puts("start - delete deletee");
  delete deletee;
  deletee = nullptr;
  puts("end");

  if (parent)
  {
    puts("start - update_size(parent)");
    parent->update_size();
    puts("end");
  }

  return ret;
}

template<class T>
auto node<T>::erase(node<T>::node_ptr tree, unsigned position, node_ptr parent, side direction)
  -> node_ptr
{
  if (!tree)
  {
    return nullptr;
  }

  auto const left_size = tree->expired_left() ? 0 : tree->left()->size();

  if (left_size == position)
  {
    return erase_node(tree, parent, direction);
  }
  else
  {
    auto const to_right = left_size < position;
    auto const subtree_pos = position - (to_right ? 1 + left_size : 0);
    auto const next_direction = to_right ? side::right : side::left;
    auto r = erase(to_right ? tree->right() : tree->left(), subtree_pos, tree, next_direction);
    (to_right ? tree->right() : tree->left()) = r;
    tree->update_size();
    return tree;
  }
}

template<class T>
auto node<T>::erase(node<T>::node_ptr tree, unsigned position)
  -> node_ptr
{
  return erase(tree, position, nullptr, side::left);
}

template<class T>
auto node<T>::nth_element(node<T>::node_ptr tree, unsigned position)
  -> node<T>::node_ptr
{
  if (!tree)
  {
    return nullptr;
  }

  auto const left_size = tree->expired_left() ? 0 : tree->left()->size();

  if (left_size == position)
  {
    return tree;
  }

  auto const to_right = left_size < position;
  auto const subtree_pos = position - (to_right ? 1 + left_size : 0);
  
  return nth_element(to_right ? tree->right() : tree->left(), subtree_pos);
}

#define TREAP_TEST

#ifdef TREAP_TEST

template<class T>
inline void debug_recur(node<T>* t, int depth = 0) {

  for(int i=0; i<depth * 2; i++)
    std::cout << " ";

  if(!t)
  {
    std::cout << "(nil)" << std::endl;
    return;
  }

  std::cout << "(" << t->value() << "[" << t->priority() << "]" << std::endl;

  debug_recur(t->left(), depth + 1);
  debug_recur(t->right(), depth + 1);

  for(int i=0; i<depth * 2; i++)
  {
    std::cout << " ";
  }

  std::cout << ")" << std::endl;
}

template<class T>
inline void debug(node<T>* t) {
  debug_recur(t);
  std::cout << "\n";
}

inline void test() {
  node<int>* root = nullptr;
  std::vector<int> vs;

  auto assert_identical = [&]()
  {
    assert(vs.size() == root->size());
    for(unsigned i=0; i<vs.size(); i++) {
      assert(vs[i] == node<int>::nth_element(root, i)->value());
    }
  };

  // INSERT
  for(int i=0; i<30; i++)
  {
    auto pos = i;
    auto val = i;
    vs.insert(vs.begin() + pos, val);
    root = node<int>::insert(root, pos, val);
    assert_identical();
  }

  std::cout << "root size = " << root->size() << std::endl;

  for(auto e: vs) std::cout << e << ", ";
  std::cout << std::endl;

  debug(root);

  // ERASE
  for(int i=0; i<3; i++)
  {
    root = node<int>::erase(root, 0);
    root->node<int>::update_size();

    puts("ERASED 0");
    puts("~~~~~~~~~~~~~~~~~");
    debug(root);
    std::cout << "size = " << root->size() << "\n";

    for(unsigned i=0; i<root->size(); i++)
    {
      printf("PRINT %dth element: ", i);
      std::cout << node<int>::nth_element(root, i)->value();
      puts("");
    }
    std::cout << std::endl;
  }

  debug(root);
}

#endif
}}} // namespace treap

#ifndef TREAP_TEST
int main()
{
  vectree::detail::treap::test();
  return 0;
}

#else

int main() {
  int N; std::cin >> N;
  vectree::vectree<int> vs;
  for(int i=0; i<N; i++) {
    int x; std::cin >> x;
    vs.push_front(x);
  }
  for(int i=0; i<N; i++) {
    std::cout << vs[i] << " \n"[i == N-1];
  }
  return 0;
}
#endif

Compiler output:
a.cc:17:1: error: expected unqualified-id before '{' token
   17 | {
      | ^
a.cc:108:35: error: 'node' in namespace 'vectree::detail::treap' does not name a template type
  108 |   using treap    = detail::treap::node<T>;
      |                                   ^~~~
a.cc:109:29: error: 'treap' has not been declared
  109 |   using node_ptr = typename treap::node_ptr;
      |                             ^~~~~
a.cc:111:3: error: 'node_ptr' does not name a type; did you mean 'mode_t'?
  111 |   node_ptr root {nullptr};
      |   ^~~~~~~~
      |   mode_t
a.cc: In destructor 'vectree::vectree::vectree<T>::~vectree()':
a.cc:119:9: error: 'root' was not declared in this scope
  119 |     if (root) { delete root; }
      |         ^~~~
a.cc: In member function 'auto vectree::vectree::vectree<T>::size() const':
a.cc:123:12: error: 'root' was not declared in this scope
  123 |   { return root ? root->size() : 0; }
      |            ^~~~
a.cc: In member function 'T vectree::vectree::vectree<T>::operator[](unsigned int) const':
a.cc:125:51: error: 'treap' has not been declared
  125 |   T operator[] (unsigned position) const { return treap::nth_element(root, position)->value(); }
      |                                                   ^~~~~
a.cc:125:70: error: 'root' was not declared in this scope
  125 |   T operator[] (unsigned position) const { return treap::nth_element(root, position)->value(); }
      |                                                                      ^~~~
a.cc: In member function 'void vectree::vectree::vectree<T>::insert(unsigned int, T)':
a.cc:130:5: error: 'root' was not declared in this scope
  130 |     root = treap::insert(root, position, val);
      |     ^~~~
a.cc:130:12: error: 'treap' has not been declared
  130 |     root = treap::insert(root, position, val);
      |            ^~~~~
a.cc: In member function 'void vectree::vectree::vectree<T>::push_back(T)':
a.cc:136:5: error: 'root' was not declared in this scope
  136 |     root = treap::insert(root, size(), val);
      |     ^~~~
a.cc:136:12: error: 'treap' has not been declared
  136 |     root = treap::insert(root, size(), val);
      |            ^~~~~
a.cc: In member function 'void vectree::vectree::vectree<T>::push_front(T)':
a.cc:142:5: error: 'root' was not declared in this scope
  142 |     root = treap::insert(root, 0, val);
      |     ^~~~
a.cc:142:12: error: 'treap' has not been declared
  142 |     root = treap::insert(root, 0, val);
      |            ^~~~~
a.cc: In member function 'void vectree::vectree::vectree<T>::erase(unsigned int)':
a.cc:148:5: error: 'root' was not declared in this scope
  148 |     root = treap::erase(root, position, nullptr);
      |     ^~~~
a.cc:148:12: error: 'treap' has not been declared
  148 |     root = treap::erase(root, position, nullptr);
      |            ^~~~~
a.cc: In member function 'void vectree::vectree::vectree<T>::clear()':
a.cc:154:9: error: 'root' was not declared in this scope
  154 |     if (root) delete root;
      |         ^~~~
a.cc:155:5: error: 'root' was not declared in this scope
  155 |     root = nullptr;
      |     ^~~~
a.cc: At global scope:
a.cc:165:10: error: expected initializer before '<' token
  165 | auto node<T>::left()
      |          ^
a.cc:170:10: error: expected initializer before '<' token
  170 | auto node<T>::right()
      |          ^
a.cc:175:10: error: expected initializer before '<' token
  175 | auto node<T>::left() const
      |          ^
a.cc:183:10: error: expected initializer before '<' token
  183 | auto node<T>::right() const
      |          ^
a.cc:191:10: error: expected initializer before '<' token
  191 | auto node<T>::child(side s)
      |          ^
a.cc:196:10: error: expected initializer before '<' token
  196 | auto node<T>::child(side s) const
      |          ^
a.cc:201:10: error: expected initializer before '<' token
  201 | auto node<T>::update_size()
      |          ^
a.cc:210:10: error: expected initializer before '<' token
  210 | auto node<T>::rotate(node<T>::node_ptr tree, side dir)
      |          ^
a.cc:222:10: error: expected initializer before '<' token
  222 | auto node<T>::insert(node<T>::node_ptr tree, unsigned position, T val)
      |          ^
a.cc:252:10: error: expected initializer before '<' token
  252 | auto node<T>::cut_link(node<T>::node_ptr parent, side s)
      |          ^
a.cc:259:10: error: expected initializer before '<' token
  259 | auto node<T>::set_least_priority(node<T>::node_ptr& deletee, node<T>::node_ptr& parent, side last_side)
      |          ^
a.cc:312:10: error: expected initializer before '<' token
  312 | auto node<T>::erase_node(node<T>::node_ptr deletee, node<T>::node_ptr parent, side last_side)
      |          ^
a.cc:338:10: error: expected initializer before '<' token
  338 | auto node<T>::erase(node<T>::node_ptr tree, unsigned position, node_ptr parent, side direction)
      |          ^
a.cc:365:10: error: expected initializer before '<' token
  365 | auto node<T>::erase(node<T>::node_ptr tree, unsigned position)
      |          ^
a.cc:372:10: error: expected initializer before '<' token
  372 | auto node<T>::nth_element(node<T>::node_ptr tree, unsigned position)
      |          ^
a.cc:398:13: error: variable or field 'debug_recur' declared void
  398 | inline void debug_recur(node<T>* t, int depth = 0) {
      |             ^~~~~~~~~~~
a.cc:398:25: error: 'node' was not declared in this scope
  398 | inline void debug_recur(node<T>* t, int depth = 0) {
      |                         ^~~~
a.cc:398:31: error: expected primary-expression before '>' token
  398 | inline void debug_recur(node<T>* t, int depth = 0) {
      |                               ^
a.cc:398:34: error: 't' was not declared in this scope
  398 | inline void debug_recur(node<T>* t, int depth = 0) {
      |                                  ^
a.cc:398:37: error: expected primary-expression before 'int'
  398 | inline void debug_recur(node<T>* t, int depth = 0) {
      |                                     ^~~
a.cc:423:13: error: variable or field 'debug' declared void
  423 | inline void debug(node<T>* t) {
      |             ^~~~~
a.cc:423:19: error: 'node' was not declared in this scope
  423 | inline void debug(node<T>* t) {
      |                   ^~~~
a.cc:423:25: error: expected primary-expression before '>' token
  423 | inline void debug(node<T>* t) {
      |                         ^
a.cc:423:28: error: 't' was not declared in this scope
  423 | inline void debug(node<T>* t) {
      |                            ^
a.cc: In function 'void vectree::vectree::detail::treap::test()':
a.cc:429:3: error: 'node' was not declared in this scope
  429 |   node<int>* root = nullptr;
      |   ^~~~
a.cc:429:8: error: expected primary-expression before 'int'
  429 |   node<int>* root = nullptr;
      |        ^~~
In file included from a.cc:8:
a.cc: In lambda function:
a.cc:434:25: error: 'root' was not declared in this scope
  434 |     assert(vs.size() == root->size());
      |                         ^~~~
a.cc:436:28: error: expected primary-expression before 'int'
  436 |       assert(vs[i] == node<int>::nth_element(root, i)->value());
      |                            ^~~
a.cc:436:28: error: expected ')' before 'int'
a.cc:436:28: error: expected ')' before 'int'
a.cc:436:7: note: to match this '('
  436 |       assert(vs[i] == node<int>::nth_element(root, i)->value());
      |       ^~~~~~
a.cc: In function 'void vectree::vectree::detail::treap::test()':
a.cc:446:5: error: 'root' was not declared in this scope
  446 |     root = node<int>::insert(root, pos, val);
      |     ^~~~
a.cc:446:17: error: expected primary-expression before 'int'
  446 |     root = node<int>::insert(root, pos, val);
      |                 ^~~
a.cc:450:34: error: 'root' was not declared in this scope
  450 |   std::cout << "root size = " << root->size() << std::endl;
      |                                  ^~~~
a.cc:455:3: error: 'debug' was not declared in this scope
  455 |   debug(root);
      |   ^~~~~
a.cc:460:17: error: expected primary-expression before 'int'
  460 |     root = node<int>::erase(root, 0);
      |                 ^~~
a.cc:461:16: error: expected primary-expression before 'int'
  461 |     root->node<int>::update_size();
      |                ^~~
a.cc:471:25: error: expected primary-expression before 'int'
  471 |       std::cout << node<int>::nth_element(root, i)->value();
      |                         ^~~
a.cc: At global scope:
a.cc:503:2: error: expected '}' at end of input
  503 | }
      |  ^
a.cc:16:19: note: to match this '{'
   16 | namespace vectree { namespace detail { namespace treap {
      |                   ^