Statement

给你一个长为 nn 的序列 aia_i，mm 次询问，每次询问给出 l,rl,r，求

min⁡i,j∈[l..r]∧i≠j{∣ai−aj∣}\min_{i, j \in [l.. r] \land i \ne j}\{|a_i - a_j|\}

数据范围：n≤105n \le 10^5，m≤3×105m \le 3 \times 10^5，0≤ai≤1090 \le a_i \le 10^9。

Solution

离线询问并按右端点升序排序，在 rr 右移的过程中维护每个 ll 的答案。每次 r−1→rr - 1 \rightarrow r 时，要加入 ara_r 和前面的数的贡献。

下面考虑 ax≥ara_x \ge a_r 的情况，ax<ara_x < a_r 的情况同理。

用主席树找到 [1..r−1][1.. r - 1] 中最大的 xx 满足 ax≥ara_x \ge a_r，更新一波 l∈[1..x]l \in [1.. x] 的答案。然后会想到继续找到 [1..x−1][1.. x - 1] 中最大的 zz 满足 ar≤az<axa_r \le a_z < a_x，然后将其作为新的 xx 更新答案并重复操作，但复杂度显然是错的。

注意到 az<axa_z < a_x，那么说明在 r=xr = x 时 ax−aza_x - a_z 一定更新过答案。那么当新的答案 az−ara_z - a_r 大于等于旧的答案 ax−aza_x - a_z 时，此次更新显然无效。所以 aza_z 必须 az<ar+ax2a_z < \frac{a_r + a_x} 2，这样每次 r−1→rr - 1 \rightarrow r 就只会有 log⁡V\log V 次更新了。

主席树以 aia_i 中的下标 ii 为时间轴，以离散化后的权值为下标，每次会在一个版本的主席树上面查询区间最大值。

用树状数组维护每个 ll 的答案即可，因为操作只有前缀 tomin\text{tomin} 和单点查询。

时间复杂度 O(nlog⁡nlog⁡V)O(n \log n \log V)，其中 VV 是值域。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
const int N = 1e5 + 7, M = 3e5 + 7, NS = 1e7 + 7, INF = 1e9;
int n, m, a[N], pp[N], rt[N], ans[M];
struct Query{ int l, r, id; } q[M];
struct SGT{
    struct Node{ int lc, rc, mx; } t[NS]; int pnodes = 0;
    #define mid ((l + r) >> 1)
    void insert(int &num, int pre, int l, int r, int p, int v) {
        t[num = ++pnodes] = t[pre], t[num].mx = std::max(t[num].mx, v);
        if(l == r) return;
        if(p <= mid) insert(t[num].lc, t[pre].lc, l, mid, p, v);
        else insert(t[num].rc, t[pre].rc, mid + 1, r, p, v);
    }
    int query(int num, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return t[num].mx;
        int s = 0;
        if(ql <= mid) s = query(t[num].lc, l, mid, ql, qr);
        if(mid < qr) s = std::max(s, query(t[num].rc, mid + 1, r, ql, qr));
        return s;
    }
} A;
int sgtquery(int p, int vl, int vr) {
    vl = std::lower_bound(pp + 1, pp + pp[0] + 1, vl) - pp;
    vr = std::upper_bound(pp + 1, pp + pp[0] + 1, vr) - pp - 1;
    if(vl > vr) return 0;
    return A.query(rt[p], 1, pp[0], vl, vr);
}
struct BIT{
    int c[N];
    void init(int n) { memset(c, 0x3f, sizeof c); }
    void modify(int x, int v) {
        while(x) c[x] = std::min(c[x], v), x -= x & -x;
    }
    int query(int x) {
        int s = INF;
        while(x <= n) s = std::min(s, c[x]), x += x & -x;
        return s;
    }
} bit;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a + i), pp[i] = a[i];
    std::sort(pp + 1, pp + n + 1);
    pp[0] = std::unique(pp + 1, pp + n + 1) - pp - 1;
    for(int i = 1, x; i <= n; i++) {
        x = std::lower_bound(pp + 1, pp + pp[0] + 1, a[i]) - pp;
        A.insert(rt[i], rt[i - 1], 1, pp[0], x, i);
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++)
        scanf("%d%d", &q[i].l, &q[i].r), ans[q[i].id = i] = INF;
    std::sort(q + 1, q + m + 1, [&](const Query &u, const Query &v) {
        return u.r < v.r;
    }), bit.init(n);
    for(int i = 1, j = 1; i <= n; i++) {
        int x = sgtquery(i - 1, a[i], INF);
        while(x) {
            bit.modify(x, a[x] - a[i]);
            x = sgtquery(x, a[i], (a[x] + a[i] - 1) / 2);
        }
        x = sgtquery(i - 1, 0, a[i]);
        while(x) {
            bit.modify(x, a[i] - a[x]);
            x = sgtquery(x, (a[x] + a[i]) / 2 + 1, a[i]);
        }
        while(j <= m && q[j].r <= i)
            ans[q[j].id] = std::min(ans[q[j].id], bit.query(q[j].l)), j++;
    }
    for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}