一、题意理解

我们有一个长度为 $n$ 的序列 $a$，$m$ 次询问，每次询问区间 $[L,R]$ 内任意两个不同位置的元素的最小绝对差： $\min_{L \le s < t \le R} |a_s - a_t|$ 如果区间长度小于 2，则输出 $2147483647$。

---

二、样例分析

样例：

n=4, a=[2,2,3,4]

• 询问 [1,2]: 元素 {2,2}，最小差 |2-2|=0
• 询问 [2,4]: 元素 {2,3,4}，最小差 |3-2|=1

---

三、问题难点

• $n \le 10^5$, $m \le 3\times 10^5$，不能对每个询问 $O(n^2)$ 暴力
• 需要高效查询任意区间的最小差值

---

四、关键观察

观察1：最小差值一定出现在排序后相邻的两个元素之间。

因此，如果我们能知道区间内排序后的相邻元素差值，最小值就是答案。

---

五、离线做法：Mo's algorithm

直接莫队复杂度 $O(n\sqrt{m} \log n)$，$n=10^5, m=3\times 10^5$ 时 $\sqrt{m} \approx 550$，总操作约 $1.65\times 10^8$，加上 set/map 的 $\log n$ 可能超时。

---

六、更优解法：只考虑有用的点对

我们只考虑那些可能成为某个区间最小差值的点对 $(i,j)$。

对于位置 $i$，可能和它组成最小差值的 $j$ 不会太多。

---

1. 寻找候选点对

对于每个 $i$，考虑它左边和右边值相近的一些位置。

具体做法：

• 对序列下标按 $a$ 值排序
• 对于每个 $i$，在排序后的数组中找它附近的几个位置，计算差值
• 这样每个位置 $i$ 只会产生 $O(1)$ 个候选点对

实际上，CF 765F 的标准做法是： 对于每个 $i$，考虑它和它左边的一些位置组成候选点对，这些位置满足某种单调性。

---

2. 候选点对的数量级

可以证明，对于每个 $i$，只需要考虑 $O(\log A)$ 个左边的位置（$A$ 是值域），就能覆盖所有可能的最小差值情况。

---

七、算法步骤（CF 765F 标准解法）

1. 生成候选点对：

   • 对数组下标按 $a$ 值排序
   • 对于每个 $i$，考虑它和它左边的一些位置 $j$，满足 $a_j$ 在某个值域区间内，且这些位置是“可能成为最小差值”的
   • 具体实现可以用值域分段或二分查找

2. 离线处理询问：

   • 将询问按右端点 $R$ 排序
   • 用线段树维护每个左端点 $L$ 的答案
   • 当右指针 $r$ 从 1 移到 $n$ 时，加入所有右端点为 $r$ 的候选点对 $(l,r)$，更新线段树在 $[1,l]$ 上的最小值

3. 回答询问：

   • 对于右端点 $R$ 的询问，在线段树上查询 $[L,R]$ 的最小值

---

八、候选点对生成细节

对于位置 $i$，我们想找到左边的一些 $j$，使得 $(j,i)$ 可能成为某个区间的最小差值。

方法：

• 维护一个候选集合 $S$
• 从右到左扫描，对于每个 $i$，考虑 $S$ 中值在 $[a_i-d, a_i+d]$ 内的元素，其中 $d$ 是当前已知的最小差值
• 更新 $d$ 并加入 $a_i$ 到 $S$

但这样复杂度仍高。优化：只考虑 $S$ 中在排序后数组里 $a_i$ 附近的一些元素。

实际上常用做法：对于每个 $i$，考虑它和它左边值最接近的 $O(\log n)$ 个位置。

---

九、代码框架（C++）

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#define ll long long
using namespace std;
const int maxn = 100010, inf = 2147483647;
struct poi {
    int l, r, pos;
} q[maxn * 3];
int n, m, x, y, z, tot, mn;
int tree[maxn << 2], a[maxn * 3], ans[maxn * 3];
set<int>s[maxn << 2];
void read(int &k) {
    int f = 1;
    k = 0;
    char c = getchar();

    while (c < '0' || c > '9')
        c == '-' && (f = -1), c = getchar();

    while (c <= '9' && c >= '0')
        k = k * 10 + c - '0', c = getchar();

    k *= f;
}
inline int abs(int x) {
    return x >= 0 ? x : -x;
}
inline int min(int a, int b) {
    return a > b ? b : a;
}
void build(int x, int l, int r) {
    tree[x] = inf;

    if (l == r)
        return;

    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
}
void update(int x, int l, int r, int cx, int delta) {
    if (l == r) {
        if (l == cx)
            return;

        tree[x] = min(tree[x], abs(a[l] - delta));
        mn = min(mn, tree[x]);
        return;
    }

    if (r <= cx) {
        set<int>::iterator it = s[x].lower_bound(delta);

        if ((it == s[x].end() || abs(*it - delta) >= mn) && (it == s[x].begin() || abs(*(--it) - delta) >= mn)) {
            mn = min(mn, tree[x]);
            return;
        }

        int mid = (l + r) >> 1;
        update(x << 1 | 1, mid + 1, r, cx, delta);
        update(x << 1, l, mid, cx, delta);
        tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
        return;
    }

    int mid = (l + r) >> 1;

    if (cx <= mid)
        update(x << 1, l, mid, cx, delta);
    else
        update(x << 1 | 1, mid + 1, r, cx, delta), update(x << 1, l, mid, cx, delta);

    tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
void pushset(int x, int l, int r, int cx, int delta) {
    s[x].insert(delta);

    if (l == r)
        return;

    int mid = (l + r) >> 1;

    if (cx <= mid)
        pushset(x << 1, l, mid, cx, delta);
    else
        pushset(x << 1 | 1, mid + 1, r, cx, delta);
}
int query(int x, int l, int r, int cl, int cr) {
    if (cl <= l && r <= cr)
        return tree[x];

    int mid = (l + r) >> 1, ret = inf;

    if (cl <= mid)
        ret = min(ret, query(x << 1, l, mid, cl, cr));

    if (cr > mid)
        ret = min(ret, query(x << 1 | 1, mid + 1, r, cl, cr));

    return ret;
}
bool cmp(poi a, poi b) {
    return a.r < b.r;
}
int main() {
    read(n);

    for (int i = 1; i <= n; i++)
        read(a[i]);

    build(1, 1, n);
    read(m);

    for (int i = 1; i <= m; i++)
        read(q[i].l), read(q[i].r), q[i].pos = i;

    sort(q + 1, q + 1 + m, cmp);

    for (int i = 1, j = 1; i <= m; i++) {
        for (; j <= q[i].r; j++) {
            mn = inf;
            update(1, 1, n, j, a[j]);
            pushset(1, 1, n, j, a[j]);
        }

        if (q[i].l == q[i].r)
            ans[q[i].pos] = inf;
        else
            ans[q[i].pos] = query(1, 1, n, q[i].l, q[i].r - 1);
    }

    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);

    return 0;
}

---

十、复杂度分析

• 候选点对总数 $O(n \log A)$
• 线段树更新和查询 $O(\log n)$
• 总复杂度 $O(n \log n \log A + m \log n)$，可以接受

---

十一、总结

本题的关键在于：

1. 最小差值一定出现在排序后相邻元素间。
2. 每个位置只需要考虑 $O(\log A)$ 个候选点对。
3. 离线按右端点排序，用线段树维护左端点答案。
4. 利用值域的单调性减少候选点对数量。
5. 该解法可以高效处理 $n \le 10^5, m \le 3\times 10^5$ 的数据范围。