洛谷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;
}