link：https://codeforces.com/contest/765/problem/F
据说是典中典问题（出现三次了）
题意：给一个序列 \(a_1,\dots,a_n\)，有 \(m\) 次询问，每次询问给 \(l,r(1\leq l<r\leq n)\)问 \(\min_{l\leq s<t\leq r}|a_s-a_t|\)
\(1\leq n,m\leq 10^5,a_i\leq 10^9\).

思路

这个做法还是很妙，想题还是先想暴力，最暴力当然是每次询问 \(O(n^2)\) 回答，太暴力了没什么用。
题目不强制在线（也没法强制），给询问离线是常见操作，离线下来随便按照右端点 \(r\) 排序，每次考虑加入一个数 \(a_i\) 产生的影响，以及如何回答所有以 \(i\) 为右端点的询问。至此应当是非常经典的套路。

这种序对的问题，可以只考虑一侧的关系（另一侧是对称的），设 \(f_i^{(r)}=\min_{i<j\leq r} |a_j-a_i|\)，扫描到 \(r\) 时查询区间最小值。那么加入一个新的元素 \(a_i\) 会如何对之前的 \(f_i\) 产生影响呢？

• \(j<i\) 且 \(a_j>a_i\)，找到满足这一条件的最大的 \(j\)（通过一棵值域线段树，\(tr[a_i]=i\)，查询区间 \([a_i+1,+\infty)\) 内的最大值），然后做单点修改。而这题的关键就在于这样的 \(j\) 并不多：
  • 设\(k<j<k\)，若 \(a_k>a_j>a_i\)，则 \(f_k\) 在插入 \(a_j\) 的时候已经被更新过了，此时不会更优；
  • 只考虑 \(a_j>a_k>a_i\)，如果要 \(a_i\) 能够影响到 \(k\)，则需要 \(a_j-a_k>a_k-a_i\)，即 \(a_k<\frac{a_i+a_j}{2}\)，带上之前的条件，就是 \(a_k\in [a_i,\lfloor \frac{a_i+a_j}{2}\rfloor]\) ，以此类推。
  • 区间长度的上界如何变化：$$\frac{a_j-a_i}{2}\to \frac{a_k-a_i}{2}<\frac{a_j-a_i}{4}\to \dots$$
  • \(O(\log V)\) 次就能跳完
• 对于\(j<i,a_j<a_i\) 的情况类似处理，同样是找最大值（因为 \(j<i\) 的限制）
  所以只需要两棵线段树：
• 值域线段树，维护为某值下标，单点赋值，区间取max
• 维护 \(f\) 的线段树，单点修改，区间取min
  如果有两个数相同怎么办？维护每个数\(a_i\) 上一次相同值出现的位置\(g_i\)，如果区间最小值 \(\geq l\) 则存在一对相同的数，答案为0

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=1e5+5;
const int MAX_A=1e9+5;
const int MAX_Q=1e5+5;
const int INF=0x3f3f3f3f;
struct Query{int l,r,idx,ans;}q[MAX_Q];
template<class T>
class Node{
public:
    int lson,rson;
    T v;
};
template<class T,typename Fun,int LOG=35>
class SegT{
    Fun f;
    Node<T> tr[N*LOG];
    T default_val;
    int cnt_node,rt,n;
    #define ls (tr[node].lson)
    #define rs (tr[node].rson)
public:
    SegT(Fun g,T v):f(g),default_val(v),rt(0){tr[0].v=default_val;}
    void init(int MX){n=MX;}
    void push_up(int node){tr[node].v=f(tr[ls].v,tr[rs].v);}
    void modify(int &node,int l,int r,int x,int v){
        if(!node){
            node=++cnt_node;
            tr[node].v=default_val;
        }
        if(l==r){
            tr[node].v=f(tr[node].v,v);
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=x)modify(ls,l,mid,x,v);
        else modify(rs,mid+1,r,x,v);
        push_up(node);
    }
    T query(int node,int l,int r,int ql,int qr){
        if(!node)return default_val;
        if(ql<=l&&r<=qr)return tr[node].v;
        int mid=(l+r)>>1;
        T ret=default_val;
        if(mid>=ql)ret=f(ret,query(ls,l,mid,ql,qr));
        if(mid+1<=qr)ret=f(ret,query(rs,mid+1,r,ql,qr));
        return ret;
    }
    void modify(int x,int v){modify(rt,1,n,x,v);}
    T query(int L,int R){return query(rt,1,n,L,R);}
};
auto mx=[](int x,int y){return x>y?x:y;};
SegT ind(mx,0),g(mx,0);
SegT f([](int x,int y){return x<y?x:y;},INF);
int main(){
    fastio;
    int n,m;
    cin>>n>>m;
    auto a=vector<int>(n+1),lst=vector<int>(n+1);
    ind.init(MAX_A);f.init(n);g.init(n);
    map<int,int> occ;
    rep(i,1,n){
        cin>>a[i];
        if(occ.count(a[i]))lst[i]=occ[a[i]];
        else lst[i]=0;
        occ[a[i]]=i;
        g.modify(i,lst[i]);
    }
    rep(i,1,m){
        cin>>q[i].l>>q[i].r;
        q[i].idx=i;
    }
    sort(q+1,q+m+1,[](Query q1,Query q2){return q1.r<q2.r;});
    int cur=0;
    rep(i,1,n){
        ind.modify(a[i],i);
        int L=1,R=MAX_A,j;
        while(a[i]<R){
            j=ind.query(a[i]+1,R);
            if(!j)break;
            f.modify(j,a[j]-a[i]);
            R=(a[i]+a[j])/2;
        }
        while(L<a[i]){
            j=ind.query(L,a[i]-1);
            if(!j)break;
            f.modify(j,a[i]-a[j]);
            L=(a[i]+a[j]+1)/2;
        }
        while(cur+1<=m&&q[cur+1].r==i){
            cur++;
            q[cur].ans=f.query(q[cur].l,q[cur].r);
            // if(g.query(q[cur].l,q[cur].r)>=q[cur].l)q[cur].ans=0;
        }
    }
    sort(q+1,q+m+1,[](Query q1,Query q2){return q1.idx<q2.idx;});
    rep(i,1,m)cout<<q[i].ans<<endl;
    return 0;
}