С наступающим, камрады. Сегодня разберём оффлайн-решение RMQ (минимум на отрезке) с помощью монотонного стека и DSU.
Задача
Дан массив a[0..n-1] и q запросов (l, r). Нужно для каждого запроса найти min(a[l..r]). Все запросы известны заранее (оффлайн).

Идея
Будем идти по правой границе r слева направо: r = 0, 1, 2, …, n-1.
В момент, когда мы дошли до позиции r, мы хотим уметь быстро отвечать на запросы, у которых правая граница равна этому r: (l, r). Если бы мы умели поддерживать для каждого l индекс минимума на отрезке [l..r], то ответ был бы просто a[minIndex].
И как раз это и будет делать DSU: после обработки r, find(l) будет возвращать индекс минимума на [l..r].
Как поддерживать минимум для всех l сразу:
Используем монотонный стек индексов. В стеке значения a по индексам идут по возрастанию (снизу вверх). Когда мы добавляем новый элемент a[r], мы выкидываем из стека все индексы x, для которых a[x] > a[r]. Получается если a[x] > a[r], то для любого отрезка, который заканчивается в r и начинается в позиции l ≤ x, элемент x уже не может быть минимумом на этом отрезке (потому что справа есть меньший a[r]). Более того, r становится “кандидатом минимума” вместо x для многих стартов l. Если просто выкидывать из стека, нам всё равно сложно понять, для каких именно l минимум “переехал” на r. Тогда с помощью DSU будем хранить переходы: если раньше минимум для l был в x, а x оказался больше нового a[r], то теперь минимум для l станет там же, где минимум для x, а это в итоге должно вести на r”. Когда индекс x вылетает из стека из-за a[r], мы делаем parent[find(x)] = r. То есть все l, которые сейчас через DSU указывают на x как на минимум, теперь должны указывать на r. После этого любой запрос (l, r) отвечается одной операцией find(l).

Тогда сгруппируем запросы по правой границе r: для каждого r храним список всех l, которые спрашивают (l, r).
Потом идём r слева направо, обновляем стек и DSU, и сразу отвечаем на все запросы с этой правой границей.

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

struct Query { int l, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // запросы сгруппированы по правой границе
    vector<vector<Query>> byR(n);
    for (int id = 0; id < q; id++) {
        int l, r;
        cin >> l >> r;
        if (l > r) swap(l, r);
        // если вход 1-based, то сделайте: --l; --r;
        byR[r].push_back({l, id});
    }

    vector<int> parent(n), ans(q);

    function<int(int)> findp = [&](int v) -> int {
        if (parent[v] == v) return v;
        return parent[v] = findp(parent[v]);
    };

    vector<int> st; // монотонный стек индексов
    st.reserve(n);

    for (int r = 0; r < n; r++) {
        parent[r] = r; // минимум на [r..r] это r

        // выкидываем всё, что больше текущего значения
        while (!st.empty() && a[st.back()] > a[r]) {
            parent[findp(st.back())] = r;
            st.pop_back();
        }
        st.push_back(r);

        // отвечаем на запросы, у которых правая граница равна r
        for (auto [l, id] : byR[r]) {
            ans[id] = a[findp(l)];
        }
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
}

Каждый индекс один раз добавляется в стек и один раз из него удаляется, значит работа со стеком O(n). DSU с сжатием путей даёт почти O(1) (обратная аккермана от n) на find, итого O((n + q) · alpha(n)).

@postupashki_prog