I.F. Souvenirs

题意简述

  • 给出 nn 以及一个长为 nn 的序列 aa。
  • 给出 mm，接下来 mm 组询问。
  • 每组询问给出一个 l,rl,r，你需要求出，对于 i,j∈[l,r]i,j \in [l,r]，且满足 i≠ji \neq j，∣ai−aj∣|a_i-a_j| 的最小值。
  • 1≤n≤1051 \leq n \leq 10^5，1≤m≤3×1051 \leq m \leq 3\times 10^5，0≤ai≤1090 \leq a_i \leq 10^9。

考虑离线处理答案，按右端点排序，每次移动右端点，处理 j<ij<i，aj>aia_j>a_i 答案。（绝对值的处理考虑拆分成单增和单减序列，处理两次就行。）

移动右端点 ii，使用权值线段树查询 j<ij<i，aj>aia_j>a_i 的最大位置 jj，但每次跳复杂度过高，需要找性质优化，由于序列具有单调性，可以考虑 j′j' 和 jj 的影响。

设 jj 为第一个最大位置，j′j' 为次大位置，此处大是下标的大，考虑每次选最优，必然满足条件如下。

{aj′−ai<aj−aiaj>aj′≥ai\begin{cases} a_{j'}-a_i<a_j-a_{i}\\ a_j>a_{j'}\ge a_i \end{cases}

考虑判断 aj′a_{j'} 范围，从上式推出（跟据所求推出的优化） aj′−ai<aj−aj′a_{j'}-a_i<a_j-a_{j'}（因为 r = ir = i 和 0 ≤ l ≤ j′0 ≤ l ≤ j' 包含 aja_j 和 aj′a_{j'}，意味着 aj−aj′a_j-a_{j'} 这对值会更新可能会更新 0 ≤ l ≤ j′0 ≤ l ≤ j' 的答案，也就是说可能是之前的最优，因此要比之前的更有），ai≤aj′<ai+aj2a_i\le a_{j'}<\frac{a_i+a_j}{2} 才是更优的。

因此复杂度降到 O(nlog⁡Alog⁡n)O(n\log A\log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
template<typename T>inline void read(T &x){
	x=0;T f=1;char ch=getchar();
	while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=getchar();}
	while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
template<typename T>inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
const int N=1e5+8;
const int M=3E5+8;
#define lowbit(x) (x)&(-x)
int t[N],a[N];
int ans[M];
int n,m;
vector<pair<int,int> > Q[N];
void update(int pos,int val){
    for(int i=pos;i;i-=lowbit(i)){
        t[i]=min(t[i],val);
    }
}
int ask(int pos){
    int res=1e9;
    for(int i=pos;i<=n;i+=lowbit(i)){
        res=min(res,t[i]);
    }
    return res;
}
int ls[N*20],rs[N*20],mx[N*20],cnt,rt;
void modify(int &u,int l,int r,int pos,int v){
    if(!u) u=++cnt;
    mx[u]=max(mx[u],v);
    if(l==r) return ;
    int mid=l+r>>1;
    if(pos<=mid) modify(ls[u],l,mid,pos,v);
    else modify(rs[u],mid+1,r,pos,v);
}
int query(int u,int l,int r,int ql,int qr){
    if(!u) return 0;
    if(ql<=l&&r<=qr) return mx[u];
    int v=0;
    int mid=l+r>>1;
    if(ql<=mid) v=max(v,query(ls[u],l,mid,ql,qr));
    if(qr>mid) v=max(v,query(rs[u],mid+1,r,ql,qr));
    return v;
}
void solve(){
    for(int i=1;i<=n;i++){
        t[i]=1e9;
    }
    for(int i=1;i<=cnt;i++){
        ls[i]=rs[i]=mx[i]=0;
    }
    cnt=rt=0;
    for(int i=1;i<=n;i++){
        int pos=query(rt,0,1e9,a[i],1e9);
        while(pos){
            update(pos,a[pos]-a[i]);
            //这里是a_j'严格小于(a_j+a_i)/2,并且满足>a_i
            pos=query(rt,0,1e9,a[i],(a[i]+a[pos])/2-(((a[i]+a[pos])%2==0)?1:0));
        }
        modify(rt,0,1e9,a[i],i);
        for(int j=0;j<Q[i].size();j++){
            ans[Q[i][j].second]=min(ans[Q[i][j].second],ask(Q[i][j].first));
        }
    }
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    read(m);
    for(int i=1;i<=m;i++){
        int l,r;
        read(l),read(r);
        ans[i]=1e9;
        Q[r].push_back({l,i});
    }
    //O(nlognlog A)
    solve();
    for(int i=1;i<=n;i++){
        a[i]=1e9-a[i];
    }
    solve();
    for(int i=1;i<=m;i++){
        write(ans[i]),putchar('\n');
    }
    return 0;
}

__END__