仔细思考发现我会(O((n+m)sqrt{n}log n))，不难发现这显然过不了
考虑一下这道题的答案是某一个点对产生的贡献，考虑强行转数点，我们将(x,y)搞成((x,y,|a_x-a_y|))
点对的个数高达(n^2)，但一些点对显然没有什么用，比如说((x_1,y_1,v_1))和((x_2,y_2,v_2))，如果存在(x_1leq x_2 leq y_2leq y_2)，并且(v_2leq v_1)，那么((x_1,y_1,v_1))显然没什么用，因为能覆盖到((x_1,y_1))的询问都能覆盖到((x_2,y_2))，并且((x_2,y_2))的答案更小
于是考虑只求出有用的点对
一个直观的想法，对于每一个(i)，先找到其前面第一个大于等于它的(j)，((j,i,a_j-a_i))是一个有用的点对，再找在(j)前面第一个比(a_j)小但大于(a_i)的位置，计入这个点对；之后将这个位置作为新的(j)如此反复
这样并没有什么复杂度的保证，但是不难发现这中间加入了很多没有意义的点对
比如说我们找到了在(j)前面第一个小于(a_j)的(k)，如果(a_j-a_kleq a_k-a_i)，那么((k,i))这个点对并没有什么用，显然((k,j))更容易被统计而且绝对答案还小
所以我们需要找的(a_k)，不仅要小于(a_j)，而且还得相对(a_j)更靠近(a_i)，也就是说(a_kin [a_i,a_j-frac{a_j-a_i}{2}])，不难发现这样每往前多形成一个点对(a_j-a_i)至少要除以(2)，也就是说一个点最多形成(log max(a_i))个点对
于是我们每次用一棵值域线段树找到(a_j)前第一个在([a_i,a_j-frac{a_j-a_i}{2}])的(a_k)，计入((k,i))这个点对，把(k)作为新的(j)继续往前找
这样只会形成(O(nlog max(a_i)))个点对，之后把询问和点对离线，扫描线+线段树统计答案即可
复杂度(O(nlog nlog max(a_i)))
代码
#include<bits/stdc++.h>
#define re register
#define LL long long
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=3e5+5;const int M=maxn*40;
inline int max(int a,int b) {return a>b?a:b;}
inline int min(int a,int b) {return a<b?a:b;}
struct pt{int x,y,v;}p[M<<1];
struct Ask{int l,r,rk;}q[maxn];
int n,m,cnt,rt,a[maxn],L,R,top,b[maxn],c[maxn],st[maxn],Ans[maxn];
inline int cmp(const pt &A,const pt &B) {return A.x>B.x;}
inline int ctp(const Ask &A,const Ask &B) {return A.l>B.l;}
struct Segment_Tree {
int l[M],r[M],tot,d[M];
inline int ins(int now,int x,int y,int pos,int v) {
if(!now) now=++tot;d[now]=v;
if(x==y) return now;
int mid=x+y>>1;
if(pos<=mid) l[now]=ins(l[now],x,mid,pos,v);
else r[now]=ins(r[now],mid+1,y,pos,v);
return now;
}
inline int query(int now,int x,int y,int lx,int ry) {
if(!now) return 0;
if(lx<=x&&ry>=y) return d[now];
int mid=x+y>>1;int t=0;
if(lx<=mid) t=max(t,query(l[now],x,mid,lx,ry));
if(ry>mid) t=max(t,query(r[now],mid+1,y,lx,ry));
return t;
}
}T;
struct Min_Segment_Tree {
int l[maxn*3],r[maxn*3],pos[maxn],d[maxn*3];
void build(int x,int y,int i) {
l[i]=x,r[i]=y;d[i]=R;
if(x==y) {pos[x]=i;return;}
int mid=x+y>>1;
build(x,mid,i<<1),build(mid+1,y,i<<1|1);
}
void add(int x,int v) {
x=pos[x];
for(;x;x>>=1) if(d[x]<=v) return;else d[x]=v;
}
int ask(int x,int y,int i) {
if(x<=l[i]&&y>=r[i]) return d[i];
int mid=l[i]+r[i]>>1;int t=R;
if(x<=mid) t=min(t,ask(x,y,i<<1));
if(y>mid) t=min(t,ask(x,y,i<<1|1));
return t;
}
}S;
int main() {
n=read();for(re int i=1;i<=n;i++) a[i]=read();
L=R=a[1];for(re int i=2;i<=n;i++) L=min(L,a[i]),R=max(R,a[i]);
for(re int i=n;i;i--) {
while(top&&a[i]>=a[st[top]]) b[st[top]]=i,top--;
st[++top]=i;
}top=0;
for(re int i=n;i;--i) {
while(top&&a[i]<=a[st[top]]) c[st[top]]=i,top--;
st[++top]=i;
}
for(re int i=1;i<=n;i++) {
if(b[i]) {
p[++cnt]=(pt){b[i],i,a[b[i]]-a[i]};
int k=a[b[i]];
while(k>a[i]) {
int t=k-std::ceil((double)(k-a[i])/2.0);
int x=T.query(rt,L,R,a[i],t);
if(!x) break;k=a[x];
p[++cnt]=(pt){x,i,a[x]-a[i]};
}
}
if(c[i]) {
p[++cnt]=(pt){c[i],i,a[i]-a[c[i]]};
int k=a[c[i]];
while(k<a[i]) {
int t=k+std::ceil((double)(a[i]-k)/2.0);
int x=T.query(rt,L,R,t,a[i]);
if(!x) break;k=a[x];
p[++cnt]={x,i,a[i]-a[x]};
}
}
rt=T.ins(rt,L,R,a[i],i);
}
m=read();for(re int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].rk=i;
std::sort(q+1,q+m+1,ctp);std::sort(p+1,p+cnt+1,cmp);
int now=1;S.build(1,n,1);
for(re int i=1;i<=m;i++) {
while(now<=cnt&&p[now].x>=q[i].l) S.add(p[now].y,p[now].v),now++;
Ans[q[i].rk]=S.ask(q[i].l,q[i].r,1);
}
for(re int i=1;i<=m;i++) printf("%d
",Ans[i]);
return 0;
}