洛谷P5926 [JSOI2009] 面试的考验题解

题目链接：P5926 [JSOI2009] 面试的考验

题意：

求区间最接近且不相等的两数之差的绝对值。最接近指数值上最接近。

输入格式：

第一行输入两个整数 \(N,Q\)，分别代表序列的长度和询问的个数。

第二行包含 \(N\) 个由一个空格分开的正整数，代表了整个序列，从左向右依次编号为 \(A_1, A_2……A_n\)。

接下来 \(Q\) 行，每行两个整数 \(i,j\) 表示了一个询问区间。

输入数据保证 \(1\le i<j\le N\)。

输出格式：

对于每一个询问输出一行，为所问区间中最接近两个数之差的绝对值。

数据范围：

\(1\le N,Q\le10^5,1\le A_i\le10^9\)。数据为全部纯随机生成。

思路是考察对答案有贡献的点对。

对于 \(i < j,~a_i < a_j\) 的点对，其中 \(i\) 固定。

如果 \(x\) 是 \(i\) 之后对答案有贡献的第一个点，则 \(a_x \in [a_i + 1, +\infty)\) 且 \(x\) 是 \([i+1,\,n]\) 中满足条件的最小的点。

如果 \(y\,(x < y)\) 是 \(i\) 之后对答案有贡献的第二个点，那么 \(a_y-a_i < a_x-a_y\)，得到 \(a_y \in [a_i + 1, \frac{a_x + a_i}{2}]\) 。

可以发现，每多加一个点对，值域就缩小一半，则 \(i\) 固定时至多 \(\mathcal{O}(\log V)\) 个点对会产生贡献。

我们可以用权值线段树维护这个东西，线段树上的每个节点维护区间最大值。

然后对于每个跳出来的 \(x\) ，这就是一个后缀最小值，可以用反向的树状数组维护。

对于 \(i < j,~a_i > a_j\) 的点对，我们可以令 \(a_i \gets \mathrm{INF} - a_i\) ，这样再跑一遍刚才的算法就可以了。

代码里写的是 \(j\) 固定时 \(i < j, a_i > a_j\) 的点对，这样写比较方便。另外记得特判 \(0\) 。

时间复杂度 \(\mathcal{O}(n \log V)\)

代码：

#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)(1e5 + 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 && v; 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 >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    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;
}