题目链接
题意：给定一个长度为n的数组与m个查询。第i个查询要求输出数组下标区间[li,ri]内的数之间的距离（差的绝对值）的最小值。
分析：离线处理查询。将查询区间按右端点从小到大排序，维护一个数据结构，使得将数组元素a1,a2,...,ai插入到数据结构之后能够快速查询以ai为右端点的查询区间的答案。考虑ai对查询区间的贡献，设d=|ai-aj|(j<i)，则对于满足l≤j,r=a[i]的查询区间[l,r]，有查询区间[l,r]的答案≤d。因此可以用线段树来维护答案，线段树每个结点记录左端点处于对应范围内时（当右端点 为ai时）的查询区间的上确界。
若暴力处理ai对查询区间的贡献，则时间复杂度为O(n)，这显然是不可接受的。不妨先设a1,a2,...,ai-1均大于等于ai（一般情况下处理2次即可），则在计算完元素对(ai,ai-1)对查询区间的贡献后，设下一个选取的元素对为(ai,aj)，则aj应满足aj≤(ai+ai-1)/2。这是因为：1.aj≥ai-1时元素对(ai,aj)不优于元素对(ai,ai-1)的贡献；2.(ai+ai-1)/2≤aj≤ai-1时元素对(ai,aj)的贡献不优于元素对(ai-1,aj)的贡献。依次类推，计算ai对查询区间的贡献时间复杂度可以优化到O(lgn)。
下面讨论程序的实现。我们需要一个数据结构，使得能够快速求出数组下标在[1,j-1]范围内大小在范围[ai,(ai+aj)/2]内的下标最大的数。可以建一棵线段树，线段树的每个结点[l,r]存一个vector，vector里将al,al+1,...,ar按从小到大排序，然后就可以O(lgn^2)地完成这件事（官方题解似乎有O(lgn)的做法）。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; struct que { int l,r,i; bool operator < (const que &o) const { return r<o.r; } }qu[maxn]; int n,m,a[maxn],ans[maxn]; vector<int> vec[maxn*4]; int minv[maxn*4],ql,qr,p,val; void build(int o,int l,int r) { if (l==r) {vec[o].push_back(a[l]);return ;} int mid=(l+r)/2; build(2*o,l,mid);build(2*o+1,mid+1,r); int i=0,j=0; while (i<vec[2*o].size()&&j<vec[2*o+1].size()) { if (vec[2*o][i]<=vec[2*o+1][j]) vec[o].push_back(vec[2*o][i]),i++; else vec[o].push_back(vec[2*o+1][j]),j++; } while (i<vec[2*o].size()) vec[o].push_back(vec[2*o][i]),i++; while (j<vec[2*o+1].size()) vec[o].push_back(vec[2*o+1][j]),j++; } int find(int o,int l,int r,int mine,int maxe) { if (ql<=l&&r<=qr) { vector<int>::iterator it=lower_bound(vec[o].begin(),vec[o].end(),mine); if (it==vec[o].end()||*it>maxe) return -1; if (l==r) return l; int mid=(l+r)/2,ret=find(2*o+1,mid+1,r,mine,maxe); if (ret!=-1) return ret; return find(2*o,l,mid,mine,maxe); } int mid=(l+r)/2,ret=-1; if (qr>mid) ret=find(2*o+1,mid+1,r,mine,maxe); if (ret!=-1) return ret; return find(2*o,l,mid,mine,maxe); } void updata(int o,int l,int r) { if (l==r) {minv[o]=min(minv[o],val);return ;} int mid=(l+r)/2; if (p<=mid) updata(2*o,l,mid); else updata(2*o+1,mid+1,r); minv[o]=min(minv[2*o],minv[2*o+1]); } int query(int o,int l,int r) { if (ql<=l&&r<=qr) return minv[o]; int mid=(l+r)/2,ret=1e9; if (ql<=mid) ret=min(ret,query(2*o,l,mid)); if (qr>mid) ret=min(ret,query(2*o+1,mid+1,r)); return ret; } int main() { cin>>n;for (int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); cin>>m;for (int i=1;i<=m;i++) scanf("%d%d",&qu[i].l,&qu[i].r),qu[i].i=i; sort(qu+1,qu+m+1); for (int i=0;i<maxn*4;i++) minv[i]=1e9; int pos=1; for (int i=2;i<=n;i++) { int j; ql=1;qr=i-1; j=find(1,1,n,a[i],1e9); while (j!=-1) { int d=a[j]-a[i]; p=j;val=d; updata(1,1,n); if (!d||j==1) break; d/=2; ql=1;qr=j-1; j=find(1,1,n,a[i],a[i]+d); } ql=1;qr=i-1; j=find(1,1,n,0,a[i]); while (j!=-1) { int d=a[i]-a[j]; p=j;val=d; updata(1,1,n); if (!d||j==1) break; d/=2; ql=1;qr=j-1; j=find(1,1,n,a[i]-d,a[i]); } while (pos<=m&&qu[pos].r==i) { ql=qu[pos].l;qr=i; ans[qu[pos].i]=query(1,1,n); pos++; } } for (int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }