仔细思考发现我会\(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_1\leq x_2 \leq y_2\leq y_2\)，并且\(v_2\leq 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_k\leq a_k-a_i\)，那么\((k,i)\)这个点对并没有什么用，显然\((k,j)\)更容易被统计而且绝对答案还小

所以我们需要找的\(a_k\)，不仅要小于\(a_j\)，而且还得相对\(a_j\)更靠近\(a_i\)，也就是说\(a_k\in [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(n\log \max(a_i))\)个点对，之后把询问和点对离线，扫描线+线段树统计答案即可

复杂度\(O(n\log n\log max(a_i))\)

代码

#include
    
     #define re register#define LL long longinline 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.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
      
       =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\n",Ans[i]);    return 0;}