lessons/参考实现/06-最小与最大生成树/CodeForces-1706E.cpp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests; cin >> tests;
    while (tests--) {
        int n, m, queries; cin >> n >> m >> queries;
        vector<int> dsu(2 * n), value(2 * n, 0);
        iota(dsu.begin(), dsu.end(), 0);
        vector<vector<int>> child(2 * n);
        auto find = [&](auto &&self, int x) -> int {
            return dsu[x] == x ? x : dsu[x] = self(self, dsu[x]);
        };
        int nodes = n;
        for (int index = 1; index <= m; ++index) {
            int u, v; cin >> u >> v; --u; --v;
            int a = find(find, u), b = find(find, v);
            if (a == b) continue;
            value[nodes] = index;
            child[nodes] = {a, b};
            dsu[a] = dsu[b] = nodes;
            dsu[nodes] = nodes;
            ++nodes;
        }
        int root = find(find, 0), log = 1;
        while ((1 << log) <= nodes) ++log;
        vector<vector<int>> up(log, vector<int>(nodes, root));
        vector<int> depth(nodes, 0), stack{root};
        while (!stack.empty()) {
            int u = stack.back(); stack.pop_back();
            for (int v : child[u]) {
                up[0][v] = u; depth[v] = depth[u] + 1; stack.push_back(v);
            }
        }
        up[0][root] = root;
        for (int j = 1; j < log; ++j) for (int v = 0; v < nodes; ++v) {
            up[j][v] = up[j - 1][up[j - 1][v]];
        }
        auto lca = [&](int u, int v) {
            if (depth[u] < depth[v]) swap(u, v);
            for (int j = log - 1; j >= 0; --j) if (depth[u] - (1 << j) >= depth[v]) u = up[j][u];
            if (u == v) return u;
            for (int j = log - 1; j >= 0; --j) if (up[j][u] != up[j][v]) {
                u = up[j][u]; v = up[j][v];
            }
            return up[0][u];
        };

        int size = 1;
        while (size < max(1, n - 1)) size <<= 1;
        vector<int> segment(2 * size, 0);
        for (int i = 0; i + 1 < n; ++i) segment[size + i] = value[lca(i, i + 1)];
        for (int i = size - 1; i > 0; --i) segment[i] = max(segment[2 * i], segment[2 * i + 1]);
        auto range_max = [&](int left, int right) {
            int answer = 0;
            for (left += size, right += size; left < right; left >>= 1, right >>= 1) {
                if (left & 1) answer = max(answer, segment[left++]);
                if (right & 1) answer = max(answer, segment[--right]);
            }
            return answer;
        };
        while (queries--) {
            int l, r; cin >> l >> r; --l;
            cout << (l + 1 == r ? 0 : range_max(l, r - 1)) << ' ';
        }
        cout << '\n';
    }
}