题解 CF765F 【Souvenirs】

考虑对于每一个右端点 r ，维护 ans_i 表示 \min |a_i-a_j|,j\in[i,r] 。

那么如果我们离线下来询问，我们要求的 [l,r] 的答案就是一段后缀的最小值。但是为了保证复杂度，事实上我们维护的 ans_i 只是保证了一段后缀的最小值就是 [l,r] 的答案，而 ans_i 是可能大于 \min |a_i-a_j|,j\in[i,r] 。

现在考虑我们把 r - 1 移动到了 r ，并且已经维护好了右端点为 r - 1 时的 ans ，满足了 [l,r] 的答案就是 ans 的一段后缀最小值，考虑接下来如何修改。

首先，暴力修改的复杂度肯定有问题。但是可以发现，由于我们求答案是算后缀的最小值，事实上有些位置是没有必要修改的。

对于每个 ans_i ，只会有 O(\log a_i) 个位置让这个位置答案必须被修改。

必须 被修改？因为有些位置是可以不用被修改的。如下图：

如图，考虑 a_i ，之前最优位置在 a_j ，当前加入了 r ，其中黑线表示 \frac{a_i+a_j} 2 的位置。

考虑加入的位置，如果在蓝色位置，明显我们必须得修改 ans_i ，同时 ans_i 的值变小了至少一半。

否则，如果修改在紫色位置，我们可以直接修改 ans_j 而不修改 ans_i ，求了后缀最小值 i 这个位置作为左端点时答案是没有问题的。

如果加入的点在 a_i 下面，画一下发现是一样的。

这样总修改的点数就是 O(n\log a)。

但是如何修改呢？可以使用线段树。这里得先修改右区间再修改左区间，且如果修改当前区间的时候更新得到的答案不如之前修改过的某个位置，就直接跳过就好了。所以我们也需要对线段树每个区间维护有序的这个区间内的所有的数。

这样实际递归下去修改的就只有上文提到的 必须被修改的位置。复杂度就是 O(n\log n\log a)。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];

struct poi {
    int l , r , idx;
} Q[MAXN] ;
bool cmp( const poi& a , const poi& b ) {
    return a.r < b.r;
}

int T[MAXN << 2]; vi S[MAXN << 2];
inline void pu( int rt ) {
    T[rt] = min( T[rt << 1] , T[rt << 1 | 1] );
}
void build( int rt , int l , int r ) {
    rep( i , l , r ) S[rt].pb( A[i] );
    sort( all( S[rt] ) );
    T[rt] = 0x3f3f3f3f;
    if( l == r ) return;
    int m = l + r >> 1;
    build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
    pu( rt );
}
int cur;
void mdfy( int rt , int l , int r , int p , int x ) {
    if( r <= p ) {
        auto it = lower_bound( all( S[rt] ) , x );
        if( it != S[rt].end() ) T[rt] = min( T[rt] , ( *it ) - x );
        if( it != S[rt].begin() ) T[rt] = min( T[rt] , x - *( it - 1 ) );
        if( T[rt] >= cur ) return;
    }
    if( l == r ) {
        cur = min( cur , T[rt] );
        return;
    }
    int m = l + r >> 1;
    if( p > m ) mdfy( rt << 1 | 1 , m + 1 , r , p , x );
    mdfy( rt << 1 , l , m , p , x );
    pu( rt );
    cur = min( cur , T[rt] );
}
int que( int rt , int l , int r , int L ) {
    if( L <= l ) return T[rt];
    int m = l + r >> 1;
    if( L <= m ) return min( T[rt << 1 | 1] , que( rt << 1 , l , m , L ) );
    else return que( rt << 1 | 1 , m + 1 , r , L );
}

int ans[MAXN];

void solve() {
    cin >> n;
    rep( i , 1 , n ) scanf("%d",A + i);
    cin >> m;
    rep( i , 1 , m ) 
        scanf("%d%d",&Q[i].l,&Q[i].r) , Q[i].idx = i;
    sort( Q + 1 , Q + 1 + m , cmp );
    build( 1 , 1 , n );
    int cc = 1;
    while( Q[cc].r <= 1 ) ++ cc;
    rep( i , 2 , n ) {
        cur = 0x3f3f3f3f;
        mdfy( 1 , 1 , n , i - 1 , A[i] );
        while( Q[cc].r == i ) ans[Q[cc].idx] = que( 1 , 1 , n , Q[cc].l ) , ++ cc;
    }
    rep( i , 1 , m ) printf("%d\n",ans[i]);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}