SyntaxPilot
Courses/Competitive Programming/Lesson 69
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 69 of 90

Treap: split and merge

queued

These are the notes for Competitive Programming episode 69. Last episode's ordered set keeps values sorted, so it can't flip a range or move a block. A treap is a binary search tree ordered by position and, at the same time, a heap by a random priority, so its expected depth is O(log n). Everything is built from two operations: split (cut off the first k elements) and merge (glue two sequences). With the position counted from subtree sizes (an implicit key) and a lazy reverse flag pushed down on the way, Playlist Flips (reverse blocks l..r) and Clipboard (cut l..r and paste it at the front) both run in O(log n) per operation. On the way we hit two real bugs: forgetting push in split (Wrong Answer on the sample) and priorities that aren't random (a chain a million nodes deep: Runtime Error, stack overflow). Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A long train stands in a train yard. Moving coaches one by one is slow, but a worker can uncouple the train between any two coaches (two shorter trains) and couple two trains end to end (one long train). To flip coaches l..r: cut before l, cut after r, turn the middle train around, and couple the three back. Turning around doesn't move every coach either: we stick a note on that part saying "runs backwards" and fix it only when somebody looks inside. Cut = split, couple = merge, the note = the lazy flag.

Problem R1 · Playlist Flips

(Written for this course.)

  • A DJ has n songs in order 1, 2, …, n.
  • q times: l r reverses the songs in positions l..r.
  • Print the final playlist. n, q ≤ 10^6, time limit 8 seconds.
8 3
2 6
1 4
3 8

Flips 2..6, 1..4, 3..8: 1 6 5 4 3 2 7 8 → 4 5 6 1 3 2 7 8 → 4 5 8 7 2 3 1 6.

Attempt 1: std::reverse on a vector (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> songs(n);
    iota(songs.begin(), songs.end(), 1);   // 1 2 3 ... n
    while (q--) {
        int l, r;
        cin >> l >> r;
        reverse(songs.begin() + l - 1, songs.begin() + r);   // touches r-l+1 songs
    }
    for (int x : songs) cout << x << " ";
}

Sample:

4 5 8 7 2 3 1 6

A million songs and a million random flips (the playlist folded into one check number):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000, q = 1000000;                 // a million songs and flips
    mt19937 gen(1);
    vector<int> songs(n);
    iota(songs.begin(), songs.end(), 1);
    while (q--) {
        int l = gen() % n + 1, r = gen() % n + 1;
        if (l > r) swap(l, r);
        reverse(songs.begin() + l - 1, songs.begin() + r);
    }
    ll check = 0;
    for (int i = 0; i < n; i++) check += (ll)(i + 1) * songs[i];
    cout << check << "\n";
}
Time Limit Exceeded

An average flip covers a third of the playlist: about 3·10^11 swaps.

Tree plus heap

  • In a vector, songs sit in one block of memory, so cutting or gluing moves elements.
  • In a binary search tree, cutting and gluing only re-link nodes along one root-to-leaf path, as long as the tree is shallow.
  • A treap gives every node a random priority. The tree is ordered by position (an in-order walk reads the sequence) and is a heap by priority (a parent's priority is bigger than its children's). With random priorities the shape is that of a random BST, so the expected depth is O(log n). No rotations and no balancing rules.

split and merge by position (the implicit key)

  • We never store positions (one flip would change millions of them). Each node stores the size of its subtree; a node's position is size(left) + 1.
  • split(t, k): if size(t->l) < k, t and its left subtree belong to the first part, and we split t->r with k − size(t->l) − 1; otherwise t and its right subtree belong to the second part and we split t->l with k.
  • merge(a, b) (every node of a comes before every node of b): the root with the higher priority stays on top; merge into its inner child (a's right, or b's left).
  • pull(t) recomputes the size after the children change.

The lazy flip

  • Flip l..r: split(root, l − 1) → a, rest; split(rest, r − l + 1) → b, c; b->rev ^= 1; root = merge(merge(a, b), c).
  • push(t): if t->rev, swap t's children and pass the flag to both. A reversed tree is the same tree with every node's children swapped.
  • Rule: push a node before you look at its children: in split, in merge, and when you read the answer.
  • A flip = 2 splits + a flag + 2 merges = O(log n) expected.

Bug 1: split without push (Wrong Answer)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    Node* root = nullptr;
    for (int i = 1; i <= n; i++) root = merge(root, new Node(i));
    while (q--) {
        int l, r;
        cin >> l >> r;
        Node *a, *b, *c;
        split(root, l - 1, a, b);         // a = songs 1..l-1
        split(b, r - l + 1, b, c);        // b = songs l..r, c = the rest
        b->rev ^= 1;                       // flip b, lazily
        root = merge(merge(a, b), c);
    }
    vector<int> songs;
    collect(root, songs);
    for (int x : songs) cout << x << " ";
}
3 5 8 7 2 4 1 6

The right answer starts with 4 5. split reads t->l and t->r before the flag is applied, so it walks into a flipped part the wrong way round.

The fix: push(t) at the top of split

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    Node* root = nullptr;
    for (int i = 1; i <= n; i++) root = merge(root, new Node(i));
    while (q--) {
        int l, r;
        cin >> l >> r;
        Node *a, *b, *c;
        split(root, l - 1, a, b);         // a = songs 1..l-1
        split(b, r - l + 1, b, c);        // b = songs l..r, c = the rest
        b->rev ^= 1;                       // flip b, lazily
        root = merge(merge(a, b), c);
    }
    vector<int> songs;
    collect(root, songs);
    for (int x : songs) cout << x << " ";
}

Sample, and one song with one flip (1 1 / 1 1):

4 5 8 7 2 3 1 6
1

A million songs and a million flips:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    int n = 1000000, q = 1000000;                 // a million songs and flips
    mt19937 gen(1);
    Node* root = nullptr;
    for (int i = 1; i <= n; i++) root = merge(root, new Node(i));
    while (q--) {
        int l = gen() % n + 1, r = gen() % n + 1;
        if (l > r) swap(l, r);
        Node *a, *b, *c;
        split(root, l - 1, a, b);         // a = songs 1..l-1
        split(b, r - l + 1, b, c);        // b = songs l..r, c = the rest
        b->rev ^= 1;                       // flip b, lazily
        root = merge(merge(a, b), c);
    }
    vector<int> songs;
    collect(root, songs);
    ll check = 0;
    for (int i = 0; i < n; i++) check += (ll)(i + 1) * songs[i];
    cout << check << "\n";
}
250206136329055792

About five seconds here for four million splits and merges: accepted within the 8-second limit. The treap's constant is large (pointer chasing and cache misses), which is why treap problems often have generous limits.

Stress test against std::reverse

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    mt19937 gen(69);
    for (int t = 1; t <= 500; t++) {
        int n = gen() % 10 + 1, q = gen() % 10 + 1;
        Node* root = nullptr;
        vector<int> slow(n);
        for (int i = 1; i <= n; i++) root = merge(root, new Node(i)), slow[i - 1] = i;
        while (q--) {
            int l = gen() % n + 1, r = gen() % n + 1;
            if (l > r) swap(l, r);
            Node *a, *b, *c;
            split(root, l - 1, a, b);         // a = songs 1..l-1
            split(b, r - l + 1, b, c);        // b = songs l..r, c = the rest
            b->rev ^= 1;                       // flip b, lazily
            root = merge(merge(a, b), c);
            reverse(slow.begin() + l - 1, slow.begin() + r);
        }
        vector<int> fast;
        collect(root, fast);
        if (fast != slow) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Bug 2: priorities that aren't random (Runtime Error)

Give each song the priority equal to its own number (pri(v) instead of pri(rng())):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(v) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    int n = 1000000, q = 1000000;                 // a million songs and flips
    mt19937 gen(1);
    Node* root = nullptr;
    for (int i = 1; i <= n; i++) root = merge(root, new Node(i));
    while (q--) {
        int l = gen() % n + 1, r = gen() % n + 1;
        if (l > r) swap(l, r);
        Node *a, *b, *c;
        split(root, l - 1, a, b);         // a = songs 1..l-1
        split(b, r - l + 1, b, c);        // b = songs l..r, c = the rest
        b->rev ^= 1;                       // flip b, lazily
        root = merge(merge(a, b), c);
    }
    vector<int> songs;
    collect(root, songs);
    ll check = 0;
    for (int i = 0; i < n; i++) check += (ll)(i + 1) * songs[i];
    cout << check << "\n";
}
Runtime Error (SIGSEGV)

Every new song has the highest priority so far, so it becomes the root with the old tree on its left: a chain a million nodes deep. The first split recurses a million levels and overflows the stack. Random priorities mean that no input order can build a chain.

Problem R2 · Clipboard

(Written for this course.)

  • The same playlist 1..n and the same limits.
  • q times: l r cuts songs l..r and pastes them at the very front.
6 2
3 5
2 4

Cut 3..5: 3 4 5 1 2 6; cut 2..4 (4 5 1): 4 5 1 3 2 6.

The obvious attempt: std::rotate (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> songs(n);
    iota(songs.begin(), songs.end(), 1);
    while (q--) {
        int l, r;
        cin >> l >> r;
        // songs l..r move to the front: shifts r songs
        rotate(songs.begin(), songs.begin() + l - 1, songs.begin() + r);
    }
    for (int x : songs) cout << x << " ";
}
4 5 1 3 2 6
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000, q = 1000000;                 // a million songs and flips
    mt19937 gen(1);
    vector<int> songs(n);
    iota(songs.begin(), songs.end(), 1);
    while (q--) {
        int l = gen() % n + 1, r = gen() % n + 1;
        if (l > r) swap(l, r);
        rotate(songs.begin(), songs.begin() + l - 1, songs.begin() + r);
    }
    ll check = 0;
    for (int i = 0; i < n; i++) check += (ll)(i + 1) * songs[i];
    cout << check << "\n";
}
Time Limit Exceeded

The treap: same splits, a different merge order

Only one line changes: root = merge(merge(b, a), c); and no flag is needed.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    Node* root = nullptr;
    for (int i = 1; i <= n; i++) root = merge(root, new Node(i));
    while (q--) {
        int l, r;
        cin >> l >> r;
        Node *a, *b, *c;
        split(root, l - 1, a, b);
        split(b, r - l + 1, b, c);
        root = merge(merge(b, a), c);      // b goes to the front
    }
    vector<int> songs;
    collect(root, songs);
    for (int x : songs) cout << x << " ";
}
4 5 1 3 2 6
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    int n = 1000000, q = 1000000;                 // a million songs and flips
    mt19937 gen(1);
    Node* root = nullptr;
    for (int i = 1; i <= n; i++) root = merge(root, new Node(i));
    while (q--) {
        int l = gen() % n + 1, r = gen() % n + 1;
        if (l > r) swap(l, r);
        Node *a, *b, *c;
        split(root, l - 1, a, b);
        split(b, r - l + 1, b, c);
        root = merge(merge(b, a), c);      // b goes to the front
    }
    vector<int> songs;
    collect(root, songs);
    ll check = 0;
    for (int i = 0; i < n; i++) check += (ll)(i + 1) * songs[i];
    cout << check << "\n";
}
249929752255272730
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    mt19937 gen(69);
    for (int t = 1; t <= 500; t++) {
        int n = gen() % 10 + 1, q = gen() % 10 + 1;
        Node* root = nullptr;
        vector<int> slow(n);
        for (int i = 1; i <= n; i++) root = merge(root, new Node(i)), slow[i - 1] = i;
        while (q--) {
            int l = gen() % n + 1, r = gen() % n + 1;
            if (l > r) swap(l, r);
            Node *a, *b, *c;
            split(root, l - 1, a, b);
            split(b, r - l + 1, b, c);
            root = merge(merge(b, a), c);      // b goes to the front
            rotate(slow.begin(), slow.begin() + l - 1, slow.begin() + r);
        }
        vector<int> fast;
        collect(root, fast);
        if (fast != slow) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Per operation Total (n = q = 10^6) Verdict
vector + reverse O(n) ~3·10^11 swaps TLE
vector + rotate O(n) ~10^11 moves TLE
treap, random priorities O(log n) expected O(q log n) accepted (~5 s)
treap, sorted priorities O(n) (a chain) stack overflow Runtime Error

Memory: one node per song, O(n). Building by merging n single nodes costs O(n log n) expected (an O(n) build with a stack exists, but isn't needed here).

Common mistakes (and the real outputs)

Mistake What you see Why Fix
split without push(t) 3 5 8 7 2 4 1 6 (expected 4 5 8 7 2 3 1 6) walks a flipped part backwards push before reading children
priority = index or value Runtime Error (SIGSEGV) the tree becomes a chain mt19937 random priority
forgetting pull(t) Wrong Answer stale sizes give wrong positions pull after changing children
split(root, l) for the block l..r off-by-one Wrong Answer split by k keeps the first k nodes split(root, l − 1)
rand() for priorities slow or skewed trees RAND_MAX can be 32767 mt19937
reading the answer without push wrong order printed flags still pending push in the in-order walk
deep recursion in the in-order walk on a bad tree Runtime Error recursion depth = tree depth random priorities (depth ~ log n)

Mini project

Build a text editor buffer on an implicit treap of characters: insert(pos, string), erase(l, r), reverse(l, r), print(). Test it against std::string on 1000 random operations, then time it on a million characters.

Practice

These are the homework problems from the episode.

1. Range sums between flips. Store sum in every node (pull adds val + sum(l) + sum(r)). A flip doesn't change any sum, so push stays the same. A query splits out l..r, prints sum(b), and merges back.

2. Insert a song at position p. split(root, p, a, b); root = merge(merge(a, new Node(x)), b).

Solution for 1 and 2 (one program: R l r flip, S l r sum, I p x insert after the first p)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    ll val, sum;
    int pri, sz = 1;
    bool rev = false;
    Node *l = nullptr, *r = nullptr;
    Node(ll v) : val(v), sum(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
ll sum(Node* t) { return t ? t->sum : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); t->sum = t->val + sum(t->l) + sum(t->r); }
void push(Node* t) {
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    Node* root = nullptr;
    for (int i = 0; i < n; i++) { ll x; cin >> x; root = merge(root, new Node(x)); }
    while (q--) {
        char op;
        cin >> op;
        if (op == 'I') {                       // I p x: insert x after the first p elements
            int p; ll x;
            cin >> p >> x;
            Node *a, *b;
            split(root, p, a, b);
            root = merge(merge(a, new Node(x)), b);
        } else {                               // R l r: flip · S l r: print the sum of l..r
            int l, r;
            cin >> l >> r;
            Node *a, *b, *c;
            split(root, l - 1, a, b);
            split(b, r - l + 1, b, c);
            if (op == 'R') b->rev ^= 1;
            else cout << sum(b) << "\n";
            root = merge(merge(a, b), c);
        }
    }
}

Input:

5 5
3 1 4 1 5
S 1 3
R 2 5
S 1 2
I 0 9
S 1 3

Output (checked against a vector brute force on 150 random tests):

8
8
17

3. Cyclic shift of a block by one (the last element of l..r moves to position l). Split into a | b (l..r−1) | c (r) | d and merge a, c, b, d. O(log n).

Hint

Three splits: split(root, l − 1), then split(rest, r − l), then split(rest2, 1).

4. An ordered multiset with a key treap. Split by value instead of position: split(t, x) puts values < x left. Insert = split by x, merge left, new node, right. Erase one copy of x = split by x, split the right part by x + 1, drop one node from the middle (merge its children), merge back. Count < x = the size of the left part.

Hint

The only change in split is the test: if (t->val < x) instead of if (sz(t->l) < k), and the recursion keeps x unchanged.

Quick quiz

// root holds 10 20 30 40 50
split(root, 2, a, b);
root = merge(b, a);
// read root left to right

A) 30 40 50 10 20 · B) 20 10 50 40 30 · C) 10 20 30 40 50 · D) 40 50 10 20 30

Answer

A. split by 2 gives a = 10 20 and b = 30 40 50. merge(b, a) puts b first: 30 40 50 10 20 (a rotation in O(log n)).

Interview questions

  1. What is a treap? A binary tree that is a BST by key (or position) and a heap by a random priority; its expected depth is O(log n).
  2. Why are the priorities random? So the shape doesn't depend on the input order; sorted priorities give a chain of depth n.
  3. What do split and merge do? split(t, k) cuts a treap into its first k nodes and the rest; merge(a, b) glues two treaps when all of a comes before all of b. Both walk one path: O(log n) expected.
  4. What is an implicit key? The position is not stored; it's computed as size(left) + 1 while walking down, so cutting and gluing never renumbers anything.
  5. How does a range reverse work? Split out the block, toggle a lazy rev flag on its root, merge back; push swaps children and passes the flag down when a node is visited.
  6. When must you call push? Before reading a node's children: in split, merge, and any walk or query.
  7. Treap vs __gnu_pbds tree? pbds is a ready ordered set by value (rank and k-th); a treap can also cut, glue, reverse and move blocks of a sequence.
  8. Treap vs segment tree? A segment tree has a fixed array of positions; an implicit treap can insert, delete and move blocks.

Glossary

Term Meaning Example
Treap Tree + heap: BST order by key/position, heap order by random priority the playlist treap
Priority A random number stored in each node pri(rng())
Heap property A parent's priority is bigger than its children's D · 95 is the root
split(t, k) Cut a treap into its first k nodes and the rest split(root, l - 1, a, b)
merge(a, b) Glue two treaps, a before b merge(merge(a, b), c)
Implicit key Position computed from subtree sizes, never stored position = size(left) + 1
Subtree size Number of nodes in a node's subtree t->sz
pull Recompute a node's size (and sums) from its children pull(t)
push Apply a node's lazy flag one level down swap children, pass rev
Lazy flag A pending change stored at a node and applied later rev
In-order walk Visit left subtree, node, right subtree: reads the sequence collect
Expected depth Average depth over the random priorities: O(log n) ~40 for 10^6 nodes
Chain A tree where every node has one child: depth n sorted priorities
Stack overflow Recursion deeper than the stack allows Runtime Error (SIGSEGV)
SIGSEGV The signal for an invalid memory access the chain crash
mt19937 C++'s Mersenne Twister random generator mt19937 rng(69)
std::reverse / std::rotate Vector algorithms, O(length) the TLE attempts
Stress test Fast solution vs a surely-correct slow one on many random inputs all 500 tests passed
Monotonic stack A stack kept sorted to find nearest smaller elements next episode

Summary

  • A treap is a BST by position plus a heap by random priority: expected depth O(log n).
  • split and merge build everything: flip = split, split, toggle rev, merge, merge; cut and paste = merge the pieces in a new order.
  • The position is size(left) + 1 (implicit key); pull after changing children, push before reading them.
  • Sorted priorities make a chain (stack overflow); missing push gives Wrong Answer.

Solutions in C++, Java and Python

Problem R1 · Playlist Flips

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    Node* root = nullptr;
    for (int i = 1; i <= n; i++) root = merge(root, new Node(i));
    while (q--) {
        int l, r;
        cin >> l >> r;
        Node *a, *b, *c;
        split(root, l - 1, a, b);         // a = songs 1..l-1
        split(b, r - l + 1, b, c);        // b = songs l..r, c = the rest
        b->rev ^= 1;                       // flip b, lazily
        root = merge(merge(a, b), c);
    }
    vector<int> songs;
    collect(root, songs);
    for (int x : songs) cout << x << " ";
}

Java (array-based nodes; checked on the sample and 12 random tests against the C++ brute force)

import java.io.*;
import java.util.*;

public class Main {
    static int[] lc, rc, val, pri, sz;
    static boolean[] rev;
    static int cnt = 0, sa, sb;                 // sa, sb = the two parts of the last split
    static Random rng = new Random(69);

    static int newNode(int v) { cnt++; val[cnt] = v; pri[cnt] = rng.nextInt(); sz[cnt] = 1; return cnt; }
    static int size(int t) { return t == 0 ? 0 : sz[t]; }
    static void pull(int t) { sz[t] = 1 + size(lc[t]) + size(rc[t]); }
    static void push(int t) {
        if (t != 0 && rev[t]) {
            int x = lc[t]; lc[t] = rc[t]; rc[t] = x;
            if (lc[t] != 0) rev[lc[t]] ^= true;
            if (rc[t] != 0) rev[rc[t]] ^= true;
            rev[t] = false;
        }
    }
    // the first k nodes go to sa, the rest to sb
    static void split(int t, int k) {
        if (t == 0) { sa = sb = 0; return; }
        push(t);
        if (size(lc[t]) < k) { split(rc[t], k - size(lc[t]) - 1); rc[t] = sa; sa = t; }
        else { split(lc[t], k); lc[t] = sb; sb = t; }
        pull(t);
    }
    static int merge(int a, int b) {
        if (a == 0 || b == 0) return a != 0 ? a : b;
        if (pri[a] > pri[b]) { push(a); rc[a] = merge(rc[a], b); pull(a); return a; }
        push(b); lc[b] = merge(a, lc[b]); pull(b); return b;
    }
    static void collect(int t, StringBuilder out) {
        if (t == 0) return;
        push(t);
        collect(lc[t], out); out.append(val[t]).append(' '); collect(rc[t], out);
    }

    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in), q = nextInt(in);
        lc = new int[n + 1]; rc = new int[n + 1]; val = new int[n + 1]; pri = new int[n + 1]; sz = new int[n + 1];
        rev = new boolean[n + 1];
        int root = 0;
        for (int i = 1; i <= n; i++) root = merge(root, newNode(i));
        while (q-- > 0) {
            int l = nextInt(in), r = nextInt(in);
            split(root, l - 1); int a = sa, rest = sb;
            split(rest, r - l + 1); int b = sa, c = sb;
            rev[b] ^= true;                          // flip b, lazily
            root = merge(merge(a, b), c);
        }
        StringBuilder out = new StringBuilder();
        collect(root, out);
        System.out.println(out.toString().trim());
    }

    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
}

Python (correct, but Python is far too slow for 10^6 operations; fine up to about 10^5)

import sys, random
sys.setrecursionlimit(10000)

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    L = [0] * (n + 1); R = [0] * (n + 1); sz = [0] * (n + 1); rev = [False] * (n + 1)
    pri = [0] + [random.random() for _ in range(n)]       # node i holds song i

    def size(t): return sz[t] if t else 0
    def pull(t): sz[t] = 1 + size(L[t]) + size(R[t])
    def push(t):
        if t and rev[t]:
            L[t], R[t] = R[t], L[t]
            if L[t]: rev[L[t]] ^= True
            if R[t]: rev[R[t]] ^= True
            rev[t] = False

    def split(t, k):                    # (first k nodes, the rest)
        if not t: return 0, 0
        push(t)
        if size(L[t]) < k:
            a, b = split(R[t], k - size(L[t]) - 1)
            R[t] = a; pull(t); return t, b
        a, b = split(L[t], k)
        L[t] = b; pull(t); return a, t

    def merge(a, b):
        if not a or not b: return a or b
        if pri[a] > pri[b]:
            push(a); R[a] = merge(R[a], b); pull(a); return a
        push(b); L[b] = merge(a, L[b]); pull(b); return b

    root = 0
    for i in range(1, n + 1):
        sz[i] = 1
        root = merge(root, i)
    pos = 2
    for _ in range(q):
        l, r = int(data[pos]), int(data[pos + 1]); pos += 2
        a, rest = split(root, l - 1)
        b, c = split(rest, r - l + 1)
        rev[b] ^= True                          # flip b, lazily
        root = merge(merge(a, b), c)

    out, stack, t = [], [], root                # in-order walk, pushing flags on the way
    while stack or t:
        while t:
            push(t); stack.append(t); t = L[t]
        t = stack.pop(); out.append(t); t = R[t]
    print(*out)

main()

Problem R2 · Clipboard

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(69);
struct Node {
    int val, pri, sz = 1;
    bool rev = false;                  // "this part is flipped"
    Node *l = nullptr, *r = nullptr;
    Node(int v) : val(v), pri(rng()) {}
};
int sz(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); }
void push(Node* t) {                   // hand the flag to the children
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
// the first k nodes go to a, the rest to b
void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else { split(t->l, k, a, t->l); b = t; }
    pull(t);
}
// every node of a comes before every node of b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { push(a); a->r = merge(a->r, b); pull(a); return a; }
    push(b); b->l = merge(a, b->l); pull(b); return b;
}
void collect(Node* t, vector<int>& out) {     // read left to right
    if (!t) return;
    push(t);
    collect(t->l, out); out.push_back(t->val); collect(t->r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    Node* root = nullptr;
    for (int i = 1; i <= n; i++) root = merge(root, new Node(i));
    while (q--) {
        int l, r;
        cin >> l >> r;
        Node *a, *b, *c;
        split(root, l - 1, a, b);
        split(b, r - l + 1, b, c);
        root = merge(merge(b, a), c);      // b goes to the front
    }
    vector<int> songs;
    collect(root, songs);
    for (int x : songs) cout << x << " ";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static int[] lc, rc, val, pri, sz;
    static boolean[] rev;
    static int cnt = 0, sa, sb;                 // sa, sb = the two parts of the last split
    static Random rng = new Random(69);

    static int newNode(int v) { cnt++; val[cnt] = v; pri[cnt] = rng.nextInt(); sz[cnt] = 1; return cnt; }
    static int size(int t) { return t == 0 ? 0 : sz[t]; }
    static void pull(int t) { sz[t] = 1 + size(lc[t]) + size(rc[t]); }
    static void push(int t) {
        if (t != 0 && rev[t]) {
            int x = lc[t]; lc[t] = rc[t]; rc[t] = x;
            if (lc[t] != 0) rev[lc[t]] ^= true;
            if (rc[t] != 0) rev[rc[t]] ^= true;
            rev[t] = false;
        }
    }
    // the first k nodes go to sa, the rest to sb
    static void split(int t, int k) {
        if (t == 0) { sa = sb = 0; return; }
        push(t);
        if (size(lc[t]) < k) { split(rc[t], k - size(lc[t]) - 1); rc[t] = sa; sa = t; }
        else { split(lc[t], k); lc[t] = sb; sb = t; }
        pull(t);
    }
    static int merge(int a, int b) {
        if (a == 0 || b == 0) return a != 0 ? a : b;
        if (pri[a] > pri[b]) { push(a); rc[a] = merge(rc[a], b); pull(a); return a; }
        push(b); lc[b] = merge(a, lc[b]); pull(b); return b;
    }
    static void collect(int t, StringBuilder out) {
        if (t == 0) return;
        push(t);
        collect(lc[t], out); out.append(val[t]).append(' '); collect(rc[t], out);
    }

    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in), q = nextInt(in);
        lc = new int[n + 1]; rc = new int[n + 1]; val = new int[n + 1]; pri = new int[n + 1]; sz = new int[n + 1];
        rev = new boolean[n + 1];
        int root = 0;
        for (int i = 1; i <= n; i++) root = merge(root, newNode(i));
        while (q-- > 0) {
            int l = nextInt(in), r = nextInt(in);
            split(root, l - 1); int a = sa, rest = sb;
            split(rest, r - l + 1); int b = sa, c = sb;
            root = merge(merge(b, a), c);            // b goes to the front
        }
        StringBuilder out = new StringBuilder();
        collect(root, out);
        System.out.println(out.toString().trim());
    }

    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
}

Python

import sys, random
sys.setrecursionlimit(10000)

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    L = [0] * (n + 1); R = [0] * (n + 1); sz = [0] * (n + 1); rev = [False] * (n + 1)
    pri = [0] + [random.random() for _ in range(n)]       # node i holds song i

    def size(t): return sz[t] if t else 0
    def pull(t): sz[t] = 1 + size(L[t]) + size(R[t])
    def push(t):
        if t and rev[t]:
            L[t], R[t] = R[t], L[t]
            if L[t]: rev[L[t]] ^= True
            if R[t]: rev[R[t]] ^= True
            rev[t] = False

    def split(t, k):                    # (first k nodes, the rest)
        if not t: return 0, 0
        push(t)
        if size(L[t]) < k:
            a, b = split(R[t], k - size(L[t]) - 1)
            R[t] = a; pull(t); return t, b
        a, b = split(L[t], k)
        L[t] = b; pull(t); return a, t

    def merge(a, b):
        if not a or not b: return a or b
        if pri[a] > pri[b]:
            push(a); R[a] = merge(R[a], b); pull(a); return a
        push(b); L[b] = merge(a, L[b]); pull(b); return b

    root = 0
    for i in range(1, n + 1):
        sz[i] = 1
        root = merge(root, i)
    pos = 2
    for _ in range(q):
        l, r = int(data[pos]), int(data[pos + 1]); pos += 2
        a, rest = split(root, l - 1)
        b, c = split(rest, r - l + 1)
        root = merge(merge(b, a), c)            # b goes to the front

    out, stack, t = [], [], root                # in-order walk, pushing flags on the way
    while stack or t:
        while t:
            push(t); stack.append(t); t = L[t]
        t = stack.pop(); out.append(t); t = R[t]
    print(*out)

main()