Codeforces

Luogu

分析

感觉很玄学的一道题。

首先将所有询问离线并按右端点排序。

假设现在右端点扫到了 $i$，考虑维护一个 $ans_j$ 表示 $[j,i]$ 的答案。

考虑用线段树维护这个 $ans$。只需要线段树上每个节点维护对应的区间内所有数，每次加一个数进来就二分一下取个 $\min$ 更新 $ans$ 即可。

这样子复杂度看起来非常的高。考虑到 $ans$ 是不降的，因此如果右边的某个区间在修改后的答案比左边的一个区间还小的话，那么左边那个区间可以不修改，对答案不会有任何影响。

这样子就可以过了...？

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=300000+10;

int n,m,a[N];
struct Query { int l,r,id; } q[M];
bool operator <(Query a,Query b) { return a.r<b.r; }
int ans[M];

#define ls (o<<1)
#define rs (o<<1|1)
vector<int> vec[N<<2];
int ansv[N<<2];
int mn;
inline void build(int o,int l,int r) {
    for (re int i=l;i<=r;++i) vec[o].push_back(a[i]);
    sort(vec[o].begin(),vec[o].end());
    ansv[o]=2e9;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
inline void modify(int o,int l,int r,int lim,int w) {
    if (r<=lim) {
        auto it=lower_bound(vec[o].begin(),vec[o].end(),w);
        if (it!=vec[o].end()) ansv[o]=min(ansv[o],*it-w);
        if (it!=vec[o].begin()) --it,ansv[o]=min(ansv[o],w-*it);
        if (mn<=ansv[o]) return;
        if (l==r) { mn=min(mn,ansv[o]); return; }
    }
    int mid=(l+r)>>1;
    if (lim>mid) modify(rs,mid+1,r,lim,w);
    modify(ls,l,mid,lim,w);
    ansv[o]=min(ansv[o],min(ansv[ls],ansv[rs]));
    mn=min(mn,ansv[o]);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return ansv[o];
    int mid=(l+r)>>1,res=2e9;
    if (ql<=mid) res=min(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=min(res,query(rs,mid+1,r,ql,qr));
    return res;
}
#undef ls
#undef rs

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    m=read();
    for (re int i=1;i<=m;++i) q[i]=(Query){read(),read(),i};
    sort(q+1,q+m+1);
    build(1,1,n);
    for (re int i=2,j=1;i<=n;++i) {
        mn=2e9,modify(1,1,n,i-1,a[i]);
        while (j<=m&&q[j].r==i) ans[q[j].id]=query(1,1,n,q[j].l,i),++j;
    }
    for (re int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}