Treap template

#include <vector>

using index = int;

struct Node {
    int value;
    int l = -1;
    int r = -1;
    int size = 0;
    bool reversed = false;
};

static std::vector<Node> mem;

int new_node(int value) {
    mem.push_back(Node{.value = value});
    return mem.size() - 1;
}

// Push delayed operations
void push_down(index node_i) {
    if (mem[node_i].reversed) {
        // ...
    }
}

// Recalculate subtree stats, e.g. size
void update(index node_i) {
    mem[node_i].size = // ...
}

std::pair<index, index> split(index node_i, int left_size) {
    push_down(node_i);
    // ...
    update(node_i);
}

index merge(index left, index right) {
    // ...
    update(result);
}

int main() {
    return 0;
}