CF765F Souvenirs 题解

题目链接：CF765F Souvenirs

题目描述：

qry 正在度假，想给两位队友买纪念品。街道上一共有 \(n\) 家纪念品商店。在第 \(i\) 家店里，qry 可以花 \(a_i\) 美元购买一件纪念品，但每家店最多只能买一件。

为了避免队友互相嫉妒，他希望购买的两件纪念品价格尽可能接近。

qry 总共逛了这条街 \(m\) 次。但在第 \(i\) 天时，只有第 \(l_i\) 到第 \(r_i\) 家店铺开门（听起来很离谱对吧？但为了设计区间查询题目的背景设定也只能这样了）。

对于每次逛街，qry 都想知道在当天开门的店铺中，能买到的两件不同纪念品的最小价格差。

换句话说，对于 qry 的每次逛街，你需要找出满足 \(l_i\le s, t \le r_i,s \ne t\) 时，\(|a_s - a_t|\) 的最小可能值。

输入格式：

第一行，一个整数 \(n\;(2\le n\le 10^5)\)。

第二行，\(n\) 个整数 \(a_1,\cdots, a_n\;(0 \le  a_i \le 10^9)\)。

第三行是，一个整数 \(m\;(1 \le m \le  3\times 10^5)\)，表示查询次数。

接下来 \(m\) 行，第 \(i\) 行包含两个整数 \(l_i,r_i\)，表示第\(i\) 天营业的店铺范围 \((1\le l_i<r_i\le n)\)。

输出格式：

对每个查询输出一行，表示答案。

做法请参考 洛谷P5926 [JSOI2009] 面试的考验 题解 。数据范围略不同，其余完全一致。

本题代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define mem(a, x) memset(a, x, sizeof(a));
#define N ((int)(3e5 + 15))
#define Fi first
#define Se second

vector<pii> q[N];
int n, m, a[N], ans[N], tr[N];
int rt, tot, ls[N * 32], rs[N * 32], mx[N * 32];
int lowbit(int x) { return x & (-x); }
void add(int x, int v) {
    for(int i = x; i; i -= lowbit(i)) down(tr[i], v);
}
int qry(int x, int r = INF) {
    for(int i = x; i <= n; i += lowbit(i)) down(r, tr[i]);
    return r; // [x, n] 
}
void update(int &at, int l, int r, int x, int v)
{
    if(!at) { at = ++tot; }
    up(mx[at], v); if(l == r) return; int mid = (l + r) >> 1;
    if(x <= mid) update(ls[at], l, mid, x, v); else update(rs[at], mid + 1, r, x, v);
}
int query(int at, int l, int r, int nl, int nr)
{
    if(!at || l > nr || r < nl) return 0;
    if(nl <= l && r <= nr) return mx[at];
    int mid = (l + r) >> 1;
    return max(query(ls[at], l, mid, nl, nr), query(rs[at], mid + 1, r, nl, nr));
}
void solve()
{
    rt = tot = 0; mem(ls, 0); mem(rs, 0); mem(mx, 0); mem(tr, 0x3f);
    for(int i = 1; i <= n; i++)
    {
        int x = query(rt, 0, INF, a[i], INF);
        while(x)
        {
            add(x, a[x] - a[i]); if(a[x] - a[i] == 0) break;
            x = query(rt, 0, INF, a[i], (a[i] + a[x]) / 2);
        }
        update(rt, 0, INF, a[i], i);
        for(pii j : q[i]) down(ans[j.Se], qry(j.Fi));
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(ans, 0x3f, sizeof(ans));
    cin >> n; for(int i = 1; i <= n; i++) cin >> a[i];
    cin >> m; for(int i = 1, l, r; i <= m; i++) { cin >> l >> r, q[r].push_back({l, i}); }
    solve(); for(int i = 1; i <= n; i++) a[i] = INF - a[i]; solve();
    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
    return 0;
}