#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;
mt19937 gen(time(0));

int fr(int limit) {
    return uniform_int_distribution<int>(0, limit-1)(gen);
}

struct Treap {
    int x;  int sz;  bool rev;
    Treap* left;  Treap* right;

    Treap (int x_) :
        x(x_), sz(1), rev(false),
        left(nullptr), right(nullptr)
    { }
};

typedef Treap* Node;

int get_sz (Node t) {
    if (t == nullptr) {return 0;}
    return t->sz;
}

void sz_recalc (Node t) {
    if (t == nullptr) return;
    t->sz = get_sz (t->left)
            + get_sz (t->right) + 1;
}

void push_rev (Node t) {
    if (!t->rev) return;
    swap (t->left, t->right);
    if (t->left != nullptr) t->left->rev ^= t->rev;
    if (t->right != nullptr) t->right->rev ^= t->rev;
    t->rev = false;
}

Node treap_merge (Node t1, Node t2) {
    if (t1 == nullptr) return t2;
    if (t2 == nullptr) return t1;

    push_rev (t1);  push_rev (t2);

    if (fr (t1->sz + t2->sz) < t1->sz) {
        // t1 is selected root
        t1->right = treap_merge (t1->right, t2);
        sz_recalc (t1);
        return t1;
    }

    // t2 is selected root
    t2->left = treap_merge (t1, t2->left);
    sz_recalc (t2);
    return t2;
}

void treap_print (Node t) {
    if (t == nullptr) return;

    push_rev(t);

    cout << "[";
    treap_print (t->left);
    cout << " (" << t->x << ", "
         << t->sz << ") ";
    treap_print (t->right);
    cout << "]";
}

pair <Node, Node> treap_split_k (Node t, int k) {
    if (t == nullptr) return {nullptr, nullptr};

    push_rev (t);

    if (k <= get_sz (t->left)) {
        auto p = treap_split_k (t->left, k);
        t->left = p.second;
        sz_recalc (t);
        return {p.first, t};
    }

    auto p = treap_split_k (t->right,
                            k - get_sz(t->left) - 1);
    t->right = p.first;
    sz_recalc (t);
    return {t, p.second};
}

Node treap_insert_k (Node t0, int k, int x0) {
    Node t = new Treap (x0);
    if (t0 == nullptr) return t;

    push_rev(t0);
    auto p = treap_split_k (t0, k);

    return treap_merge(
        p.first,
        treap_merge (t, p.second)
    ); 
}

Node set_rev (Node t, int lo, int hi) {
    auto p_hi = treap_split_k (t, hi);
    auto p_lo = treap_split_k (p_hi.first, lo);
    if (p_lo.second != nullptr) p_lo.second->rev ^= true;
    return treap_merge(treap_merge(p_lo.first, p_lo.second), p_hi.second);
}


int depth (Node t) {
    if (t == nullptr) return 0;
    return max (depth (t->left), depth (t->right)) + 1;
}

int main ( ) {
    Node t0 = new Treap (0);
    for (int i=1; i<13; i++) t0 = treap_insert_k (t0, t0->sz, i);
    treap_print(t0);  cout << endl;
    Node t1 = set_rev (t0, 4, 8);
    treap_print(t1);  cout << endl;
    return 0;
}