一、题目重述

给定长度为 $n$ 的数组 $a$，以及 $m$ 个查询 $(l_i, r_i)$。
每个查询要求：

即区间 $[l_i, r_i]$ 内任意两个不同元素的最小绝对差。

数据范围：$n \le 10^5$，$m \le 3 \times 10^5$，$a_i \le 10^9$。

二、核心难点

• 区间最小差问题，不能直接套用 RMQ
• 需要高效回答大量区间查询（$3\times10^5$）
• 支持离线，不支持在线修改

三、关键性质

性质 1：若我们固定右端点 $r$，则对于每个左端点 $l$，$[l, r]$ 的最小差值可以递推维护。

性质 2：当右端点从 $r-1$ 移动到 $r$ 时，只有与新元素 $a_r$ 最接近的两个元素（前驱和后继）会影响之前的所有左端点 $l$。

性质 3：前驱：小于 $a_r$ 的最大值；后继：大于 $a_r$ 的最小值。
因为任意其他元素与 $a_r$ 的差 ≥ 前驱/后继与 $a_r$ 的差。

四、算法思路：离线 + 线段树

4.1 基本框架

1. 将所有查询按右端点 $r$ 从小到大排序。
2. 维护一个线段树，其中 $tree[l]$ 表示当前右端点下，以 $l$ 为左端点的区间 $[l, curR]$ 的最小差值。
3. 当右端点从 $r-1$ 移动到 $r$ 时：
   • 找到 $a_r$ 在已出现元素中的前驱和后继
   • 对于每个前驱/后继的位置 $p$，区间 $[1, p]$ 的左端点都可以用 $|a_r - a_p|$ 更新（因为 $[p, r]$ 产生了新的更小差值）
   • 用线段树的区间更新（取最小值）来维护
4. 处理所有右端点 $= r$ 的查询，答案 = 线段树区间 $[l, r]$ 的最小值。

4.2 为什么只更新前驱和后继

设前驱位置为 $p$，值为 $a_p$。
对于任意左端点 $l \le p$，区间 $[l, r]$ 包含 $a_p$ 和 $a_r$，因此差值 $\le a_r - a_p$。
而且 $a_r - a_p$ 是所有 $a_r$ 与左边元素的差值中最小的，所以只更新它即可。

同理处理后继。

4.3 线段树的维护

• 线段树每个节点维护对应区间的最小差值
• 支持操作：
  • 单点更新（将 $tree[pos]$ 更新为 $min(tree[pos], val)$）
    实际上这里是对左端点 $l$ 的更新，$l$ 范围是 $[1, p]$，所以是区间取最小值。
• 查询：区间最小值

五、复杂度分析

• 排序查询：$O(m \log m)$
• 每个 $r$ 找前驱后继：使用 std::map 或 std::set，$O(\log n)$
• 每次更新：线段树区间取最小值 $O(\log n)$
• 每个查询：$O(\log n)$
• 总复杂度：$O((n + m) \log n)$，对于 $n=10^5, m=3\times10^5$ 完全可行。

六、最终代码（标程）

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

const int N = 1e5 + 5;
const int M = 3e5 + 5;
const int INF = 1e9 + 10;

int n, m;
int a[N];
int ans[M];

struct Query {
    int l, r, id;
    bool operator<(const Query& other) const {
        return r < other.r;
    }
} q[M];

// 线段树：维护区间最小值
int tr[N << 2];

void build(int u, int l, int r) {
    tr[u] = INF;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void update(int u, int l, int r, int pos, int val) {
    if (l == r) {
        tr[u] = min(tr[u], val);
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        update(u << 1, l, mid, pos, val);
    else
        update(u << 1 | 1, mid + 1, r, pos, val);
    tr[u] = min(tr[u << 1], tr[u << 1 | 1]);
}

int query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[u];
    int mid = (l + r) >> 1;
    int res = INF;
    if (ql <= mid) res = min(res, query(u << 1, l, mid, ql, qr));
    if (qr > mid) res = min(res, query(u << 1 | 1, mid + 1, r, ql, qr));
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q, q + m);
    
    // 记录每个值最近出现的位置
    map<int, int> last_pos;
    build(1, 1, n);
    
    int idx = 0;
    for (int r = 1; r <= n; ++r) {
        int x = a[r];
        
        // 找前驱（小于 x 的最大值）
        auto it = last_pos.lower_bound(x);
        if (it != last_pos.end()) {
            update(1, 1, n, it->second, it->first - x);
        }
        // 找后继（大于 x 的最小值）
        if (it != last_pos.begin()) {
            --it;
            update(1, 1, n, it->second, x - it->first);
        }
        
        last_pos[x] = r;
        
        // 处理所有右端点为 r 的查询
        while (idx < m && q[idx].r == r) {
            ans[q[idx].id] = query(1, 1, n, q[idx].l, r);
            ++idx;
        }
    }
    
    for (int i = 0; i < m; ++i) {
        cout << ans[i] << "\n";
    }
    
    return 0;
}

七、正确性说明

• 当右端点固定为 $r$ 时，线段树 $tree[l]$ 存储了区间 $[l, r]$ 的最小差值
• 每次加入新元素 $a_r$，只可能通过与其最接近的两个元素产生更小的差值
• 更新这些差值到所有包含这两个元素位置的左端点
• 查询时直接取区间最小值

八、注意事项

• 使用 map 维护每个值最近出现的位置，保证前驱后继的 $O(\log n)$ 查找
• 线段树采用单点取 min 更新（因为每个位置只会被更新有限次）
• 初始化线段树为 INF，表示未计算