本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-03 07:59:31

询问区间最小差。

离线处理。只考虑 $i<j,a_i\leq a_j$ 的情况

考虑对于 $i$ ，有哪些 $j$ 能造成贡献。

注意到这些 $j$ 是在只保留大于等于 $a_i$ 值后的单调队列样式的单调上升序列。

即为 $i$ 左侧第一个大于等于 $a_i$ 的 $a_{j_1}$ ，$a_{j_1}$ 左侧第一个小于 $a_{j_1}$ 但大于等于 $a_i$ 的 $a_{j_2}$ 等等。

容易发现如果 $a_{j_x}$ 跟 $a_{j_y}$ $(j_y<j_x)$ 间距离小于等于 $a_{j_y}$ 与 $a_i$ 的距离时，$i$ 是不会对 $j_y$ 产生贡献的。因为 $[j_y,j_x]$ 是更优且被严格包含的区间。

可以产生贡献的 $a_{j_y}$ 满足的式子是 $a_{j_x}-a_{j_y}> a_{j_y}-a_i$ 。移项后得 $a_{j_y} <\frac{a_{j_x}+a_i}{2}$ 。

且其一定满足 $a_{j_y}\geq a_i$ 。

用扫描线找一下值域范围内 $i$ 左边最靠右的下标即可。

考虑 $a_j-a_i$ 是每次至少缩小一半的，所以最多有 $\mathrm{O(\log{V})}$ 个位置能贡献到 $i$ 。

前面扫描线有一个 $\mathrm{O(\log{n})}$ ，所以总复杂度就是 $\mathrm{O(n\log{n}\log{V}+q\log{n})}$ 。

code

\/\/省略了两棵线段树。T是单点赋值区间min，T2是单点赋值区间max。

struct Que{
	int l,r,id;
	bool operator<(Que ano)const{
		return r<ano.r;
	}
}Q[N];

int X[N],len;

int a[N];

int ans[N];

void calc(int n,int m){
	T.build(1,1,n);T2.build(1,1,len);T2.n=len;
	for(int i=1,j=1;i<=n;i++){
		int limit=inf;
		while(1){
			int tmp=upper_bound(X+1,X+1+len,limit)-X-1;
			if(X[tmp]<a[i])
				break;
			int nw=T2.query(a[i],tmp);
			if(nw<=0)
				break;
			T.update(nw,X[a[nw]]-X[a[i]]);
			limit=(X[a[nw]]+X[a[i]]+1)\/2-1;
		}
		T2.update(a[i],i);
		while(j<=m&&Q[j].r==i){
			ans[Q[j].id]=min(ans[Q[j].id],T.query(Q[j].l,i));
			j++;
		}
		\/\/cout<<i<<endl;
		\/\/for(int k=1;k<=i;k++)
		\/\/	print(T.query(k,k)),pc(' ');pc('\n');
	}\/\/cout<<endl;
}

signed main(){
	int n=read();T.n=n;
	for(int i=1;i<=n;i++)
		X[i]=a[i]=read();
	sort(X+1,X+1+n);len=unique(X+1,X+1+n)-X-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(X+1,X+1+len,a[i])-X;
	int m=read();
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		Q[i]={l,r,i};
	}
	sort(Q+1,Q+1+m);
	a[0]=-1;
	memset(ans,0x3f,sizeof(ans));
	calc(n,m);
	reverse(a+1,a+1+n);
	for(int i=1;i<=m;i++){
		int l=Q[i].l,r=Q[i].r;
		Q[i].l=n-r+1,Q[i].r=n-l+1;
	}
	sort(Q+1,Q+1+m);
	calc(n,m);
	for(int i=1;i<=m;i++)
		print(ans[i]),pc('\n');
	return 0;
}