思路与算法

先对逆排列位置做ST表。相邻位置i,i+1的两个值之间所有数字都必须出现于任何包含它们的连续数字区间，得到必含位置段[L_i,R_i]。把它作为对段中所有相邻位置的依赖，利用ST最值把当前段替换为这些段的并集，每轮将可达依赖长度倍增，最多logn轮稳定。查询[x,y]取相邻闭包i=x至y-1的最小L和最大R。

正确性说明

位置区间的相邻值域联合连接其最小值到最大值。若其中任何中间数字位置不在区间，就不是连续数字；补入全部相关位置并继续闭包正是最小可行扩张。每个依赖段包含自身，所有可达相邻位置始终构成一个区间；一轮聚合等价把依赖可达步数翻倍，有限n点图用logn轮覆盖全部。重叠的连续数字区间的并仍连续，因此查询所涉相邻最小闭包的并恰为最小包含区间。

复杂度

ST建表O(nlogn)，logn轮每次ST重建O(nlogn)、扩张O(n)，总O(nlog²n+q)，空间O(nlogn)；每次查询O(1)。初始化和逆排列预处理包含在内。

易错点

依赖节点是相邻位置，聚合范围为[L,R-1]而非[L,R]。x=y时自身一格总合法，直接输出。闭包比较位置上下界，不是直接输出值域最小最大。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), pos(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        --a[i];
        pos[a[i]] = i;
    }
    int LG = 1;
    while ((1 << LG) <= n)
        LG++;
    vector<int> lg(n + 1);
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
    auto build = [&](const vector<int> &x, bool mx) {
        vector<vector<int>> st(LG, x);
        for (int k = 1; k < LG; k++)
            for (int i = 0; i + (1 << k) <= n; i++)
                st[k][i] = mx ? max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))])
                              : min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        return st;
    };
    auto get = [&](const vector<vector<int>> &s, int l, int r, bool mx) {
        int k = lg[r - l + 1];
        return mx ? max(s[k][l], s[k][r - (1 << k) + 1]) : min(s[k][l], s[k][r - (1 << k) + 1]);
    };
    auto pmin = build(pos, false), pmax = build(pos, true);
    vector<int> L(n), R(n);
    for (int i = 0; i < n - 1; i++) {
        int x = min(a[i], a[i + 1]), y = max(a[i], a[i + 1]);
        L[i] = get(pmin, x, y, false);
        R[i] = get(pmax, x, y, true);
    }
    L[n - 1] = R[n - 1] = n - 1;
    for (int step = 1; step < n; step *= 2) {
        auto mn = build(L, false), mx = build(R, true);
        vector<int> l = L, r = R;
        for (int i = 0; i < n - 1; i++) {
            l[i] = get(mn, L[i], R[i] - 1, false);
            r[i] = get(mx, L[i], R[i] - 1, true);
        }
        bool same = l == L && r == R;
        L.swap(l);
        R.swap(r);
        if (same)
            break;
    }
    auto mn = build(L, false), mx = build(R, true);
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        if (x == y)
            cout << x + 1 << ' ' << y + 1 << '\n';
        else
            cout << get(mn, x, y - 1, false) + 1 << ' ' << get(mx, x, y - 1, true) + 1 << '\n';
    }
}