Tree heap (Treap)

treap.cpp

#include <bits/stdc++.h>

using namespace std;

class Treap {
   private:
    struct Node {
        int priority;
        int count;
        int value;
        Node *left, *right;

        Node(int v)
            : priority(getRandomPriority()),
              count(1),
              value(v),
              left(nullptr),
              right(nullptr) {}

        static int getRandomPriority() {
            static mt19937 engine(random_device{}());
            static uniform_int_distribution<int> dist(0, 1'000'000'000);
            return dist(engine);
        }
    };

    Node* root;

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

    void updateCount(Node* node) {
        if (node) {
            node->count = 1 + getSize(node->left) + getSize(node->right);
        }
    }

    void split(Node* t, Node*& l, Node*& r, int k, int add = 0) {
        if (!t) {
            l = r = nullptr;
            return;
        }

        int cur_key = add + getSize(t->left);

        if (k > cur_key) {
            split(t->right, t->right, r, k, cur_key + 1);
            l = t;
        } else {
            split(t->left, l, t->left, k, add);
            r = t;
        }
        
        updateCount(t);
    }

    void merge(Node*& t, Node* l, Node* r) {
        if (!l || !r) {
            t = l ? l : r;
        } else if (l->priority > r->priority) {
            merge(l->right, l->right, r);
            t = l;
        } else {
            merge(r->left, l, r->left);
            t = r;
        }

        updateCount(t);
    }

    void buildVector(Node* node, vector<int>& v) {
        if (!node) {
            return;
        }

        buildVector(node->left, v);
        v.push_back(node->value);
        buildVector(node->right, v);
    }

    void deleteAll(Node* node) {
        if (!node) {
            return;
        }

        deleteAll(node->left);
        deleteAll(node->right);

        delete node;
    }

   public:
    Treap() : root(nullptr) {}

    ~Treap() {
        deleteAll(root);
    }

    void pushBack(int v) {
        Node* new_node = new Node(v);
        merge(root, root, new_node);
    }

    void moveRangeToEnd(int l, int r) {
        int n = getSize(root);

        if (l < 0 || r >= n || l > r) {
            return;
        }

        Node *part_before_and_range, *part_after;
        split(root, part_before_and_range, part_after, r + 1);

        Node *part_before, *part_range;
        split(part_before_and_range, part_before, part_range, l);

        merge(root, part_before, part_after);
        merge(root, root, part_range);
    }

    vector<int> toVector() {
        vector<int> v;
        buildVector(root, v);

        return v;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    int n, q;
    string s;

    cin >> n >> q >> s;

    Treap treap;

    for (char c : s) {
        treap.pushBack(c);
    }

    while (q--) {
        int l, r;
        cin >> l >> r;

        treap.moveRangeToEnd(l - 1, r - 1);
    }

    vector<int> ans = treap.toVector();

    for (int i = 0; i < ans.size(); ++i) {
        cout << char(ans[i]);
    }
    cout << '\n';
}