题目描述
给定 $n$ 个数 $a_1,a_2,\cdots,a_n$，每次询问一个区间 $[l,r]$ 内差值最小的两个数的差值。
思路
考虑离线询问，将询问按照右端点排序，然后维护左端点的答案。我们先只统计对于 $j < i, a_j > a_i$ 的贡献，对于 $a_j < a_i$ 的贡献，我们把权值全部取反再做一次就行了。
设当前的右端点位于 $i$，我们就需要找对于满足 $a_j > a_i, j < i$ 的最大的 $j$，更新左端点区间 $[1,j]$ 的答案，然后找一个 $a_i < a_{j’} < a_j,j'<j$ 的点，一直这么做下去。
注意找直接这样更新复杂度是不正确的，我们需要减少向左查询的次数。发现下一次寻找的 $j’$ 除了满足以上所说的条件之外，还需要满足 $a_j − a_{j’} > a_{j’} − a_i$，否则这次更新是没有意义的。这个判断保证每次查询都使得 $a_{j’}-a_{i}$ 减半，复杂度降至 $\Theta(n\log n\log 10^9)$。
代码
#include <bits/stdc++.h>
#define maxn 100100
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define mid ((l+r)>>1)
#define inf 0x3f3f3f3f
inline void dec(int &x,int y){x=min(x,y);}
inline void inc(int &x,int y){x=max(x,y);}
int n,m,rt[maxn],a[maxn],ans[maxn*3];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return flag?x:-x;
}
struct Ask{
int l,r,id;
Ask(int a=0,int b=0,int c=0){
l=a,r=b,id=c;
}
bool operator < (const Ask &c) const{
return r<c.r;
}
}A[maxn*3];
struct Bit{
int t[maxn];
inline void add(int x,int k){while(x)dec(t[x],k),x-=(x&-x);}
inline int sum(int x){int r=inf;while(x<=n)dec(r,t[x]),x+=(x&-x);return r;}
}B;
struct Prt{
int t[maxn*35],ls[maxn*35],rs[maxn*35],cnt;
void clear(){
memset(t,0,sizeof(t));cnt=0;
memset(ls,0,sizeof(ls));memset(rs,0,sizeof(rs));
}
inline void update(int &p,int pre,int l,int r,int pos,int val){
ls[p=++cnt]=ls[pre],rs[p]=rs[pre],inc(t[p],val);
if (l==r) return;
if (mid>=pos) update(ls[p],ls[pre],l,mid,pos,val);
else update(rs[p],rs[pre],mid+1,r,pos,val);
}
inline int query(int p,int l,int r,int L,int R){
if (L>R||!p) return 0;
if (L<=l&&r<=R) return t[p];
int res=0;
if (mid>=L) inc(res,query(ls[p],l,mid,L,R));
if (mid<R) inc(res,query(rs[p],mid+1,r,L,R));
return res;
}
}T;
inline void Solve(){
T.clear();
memset(B.t,inf,sizeof(B.t));
for (register int i=1;i<=n;++i)
T.update(rt[i],rt[i-1],1,inf,a[i],i);
int pos=1;
for (register int i=1;i<=n;++i){
int cur=T.query(rt[i-1],1,inf,a[i],inf);
while(cur){
B.add(cur,a[cur]-a[i]);
cur=T.query(rt[cur-1],1,inf,a[i],(a[cur]+a[i])/2-((a[i]+a[cur]+1)&1));
}
while(pos<=m&&A[pos].r==i) dec(ans[A[pos].id],B.sum(A[pos].l)),pos++;
}
}
int main(){
n=read();
for (register int i=1;i<=n;++i)
a[i]=read();
m=read();
for (register int i=1,l,r;i<=m;++i){
l=read(),r=read();
A[i]=Ask(l,r,i);
}
std::sort(A+1,A+1+m);
memset(ans,0x3f,sizeof(ans));
Solve();
for (register int i=1;i<=n;++i) a[i]=inf-a[i];
Solve();
for (register int i=1;i<=m;++i)
printf("%d\n",ans[i]);
}