【题解】Closest Equals

题：https://ac.nowcoder.com/acm/problem/110867
题意：给定n个数序列，m个询问[l,r]问l~r中距离最短的且a[x]==ay，输出最短距离（n,m<=5e5）
分析：

• 同一种数的话只需要和其相邻比较；
• 其次，思考怎么这个pair会在选定的范围内；
• 考虑离线处理查询，以r作为排序基准，那么只需要在某对pair的左边处添加这对pair的贡献，然后线段树搜查询范围查询[l,r]最小值即可。
• 时间复杂度：mlogn+nlogn
• （主要思考：区间贡献询问到且不影响区间查询）
  Code：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define MP make_pair
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
typedef long long ll;
const int mod=1e9+7;
const int M=5e5+5;
const int inf=0x3f3f3f3f;
const ll INF=1e18;

int a[M],ans[M];
struct node{
    int l,r,id;
}q[M];
unordered_map<int,int>lastpos;
struct SegTree{
    int tr[M<<2];
    void push_up(int root){
        tr[root]=min(tr[root<<1],tr[root<<1|1]);
    }
    void build(int root,int l,int r){
        if(l==r){
            tr[root]=inf;
            return ;
        }
        int midd=(l+r)>>1;
        build(lson);
        build(rson);
        push_up(root);
    }

    void Modify(int pos,int c,int root,int l,int r){
        if(l==r){
            tr[root]=c;
            return ;
        }
        int midd=(l+r)>>1;
        if(pos<=midd)
            Modify(pos,c,lson);
        else
            Modify(pos,c,rson);
        push_up(root);
    }
    int query(int L,int R,int root,int l,int r){
        if(L<=l&&r<=R){
            return tr[root];
        }
        int midd=(l+r)>>1;
        int res=inf;
        if(L<=midd)
            res=min(res,query(L,R,lson));
        if(R>midd)
            res=min(res,query(L,R,rson));
        return res;
    }
}t1;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+1+m,[&](node A,node B){
        if(A.r==B.r)
            return A.l<B.l;
        return A.r<B.r;
    });

    t1.build(1,1,n);
    int nowi=1;
    for(int i=1;i<=m;i++){
        while(nowi<=q[i].r){
            int tmp=lastpos[a[nowi]];
            lastpos[a[nowi]]=nowi;
            if(tmp!=0)
                t1.Modify(tmp,nowi-tmp,1,1,n);
            nowi++;
        }
        ans[q[i].id]=t1.query(q[i].l,q[i].r,1,1,n);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]==inf?-1:ans[i]);
    return 0;
}