题意：
给一个长度为n序列。m个询问(l,r)，询问min(abs(ai-aj))(l<=i< j<=r)。
n<=10^5
m<=3*10^5

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 110000
#define M 310000
#define inf 1e9
using namespace std;
struct node{int l,r,lc,rc,mi;}lt[2*N];
struct node1{int lc,rc,cnt;};
struct node2{int l,r,id;}q[M];
struct node3{int d,id,k;}A[N];
struct permanent_seg{node1 lt[N*30];int rt[N],tl;void build(int &x,int y,int k,int l,int r){x=++tl;lt[x]=lt[y];lt[x].cnt++;if(l==r) return;int mid=(l+r)/2;if(mid>=k) build(lt[x].lc,lt[y].lc,k,l,mid);else build(lt[x].rc,lt[y].rc,k,mid+1,r);}int find(int x,int y,int l,int r,int ll,int rr){if(l>r) return -1;int mid=(ll+rr)/2;if(lt[x].cnt-lt[y].cnt==0) return -1;if(ll==rr) return ll;if(mid>=r) return find(lt[x].lc,lt[y].lc,l,r,ll,mid);else if(l>mid) return find(lt[x].rc,lt[y].rc,l,r,mid+1,rr);else{int t=find(lt[x].rc,lt[y].rc,mid+1,r,mid+1,rr);if(t!=-1) return t;return find(lt[x].lc,lt[y].lc,l,mid,ll,mid);}}
}T;
int n,m,a[N],ans[M],r[N],o[N],tl;
void init()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&m);for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;for(int i=1;i<=m;i++) ans[i]=inf;
}
bool cmp(node3 x,node3 y)
{if(x.d<y.d) return 1;return 0;
}
bool cmp1(node2 x,node2 y)
{if(x.r<y.r) return 1;return 0;
}
void lsh()
{for(int i=1;i<=n;i++) A[i].d=a[i],A[i].id=i;sort(A+1,A+n+1,cmp);A[1].k=1;for(int i=2;i<=n;i++)if(A[i].d!=A[i-1].d) A[i].k=A[i-1].k+1;else A[i].k=A[i-1].k;for(int i=1;i<=n;i++) r[A[i].id]=A[i].k,o[A[i].k]=A[i].d;
}
void bt(int l,int r)
{int now=++tl;lt[now].l=l;lt[now].r=r;lt[now].lc=lt[now].rc=0;lt[now].mi=inf;if(l<r){int mid=(l+r)/2;lt[now].lc=tl+1;bt(l,mid);lt[now].rc=tl+1;bt(mid+1,r);}
}
void change(int now,int l,int r,int d)
{int mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;if(lt[now].l==l && lt[now].r==r) {lt[now].mi=min(lt[now].mi,d);return;}if(mid>=r) change(lc,l,r,d);else if(l>mid) change(rc,l,r,d);else change(lc,l,mid,d),change(rc,mid+1,r,d);
}
int find(int now,int k)
{int mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;if(lt[now].l==lt[now].r) return lt[now].mi;if(mid>=k) return min(lt[now].mi,find(lc,k));else return min(lt[now].mi,find(rc,k));
}
int td(int l,int r,int d)
{int k=-1;while(l<=r){int mid=(l+r)/2;if(o[mid]>=d) k=mid,r=mid-1;else l=mid+1;}return k;
}
void ins(int i)
{int x=r[i],y=1,p;p=T.find(T.rt[x],T.rt[y-1],1,i-1,1,n);while(p!=-1){y=r[p];int d=o[y]+(o[x]-o[y])/2+1;int k=td(y,x,d),p1=-1;if(k!=-1) p1=T.find(T.rt[x],T.rt[k-1],1,p-1,1,n);if(p1!=-1) change(1,p1+1,p,a[i]-a[p]);else change(1,1,p,a[i]-a[p]);p=p1;}
}
void solve()
{lsh();T.tl=0;for(int i=1;i<=n;i++){int k=A[i].k;if(A[i].k!=A[i-1].k) T.rt[k]=T.rt[k-1];T.build(T.rt[k],T.rt[k],A[i].id,1,n);}tl=0;bt(1,n);sort(q+1,q+m+1,cmp1);int j=1;for(int i=1;i<=n;i++){ins(i);while(j<=m && q[j].r==i){ans[q[j].id]=min(ans[q[j].id],find(1,q[j].l));j++;}if(j>m) break;}
}
int main()
{init();solve();for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);for(int i=1;i<=m;i++){int l=n-q[i].r+1,r=n-q[i].l+1;q[i].l=l;q[i].r=r;}solve();for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}

题解：
膜了题解。。
讨论右端点较大的情况，左端点较大同理
考虑右端点右移，维护所有左端点答案
当移到位置i时，需要用ai去更新答案
先找到离i最近的一个j，使ai>aj，这时ai-aj能用来更新[1,j]
再考虑j前面的一个k(j>k，ai>ak)
脑补一下，如果ak太小了，那么用abs(aj-ak)会比abs(ai-ak)更优
算一下有效的ak取值范围，是((aj+ai)/2,ai)
发现这个区间长度最多为之前的一半
这是很微妙的一件事，代表最多有log个有效的更新位置
于是每次找最靠后的合法位置，用线段树区间更新答案就行了
复杂度O(n log^2n)
关于找合法位置的实现，我用的是对权值开位置的可持久化线段树。。