522-D 题目大意
给定一个长为\(n\)的序列\(a\)，现有\(q\)个查询，每个查询\(q_i\)给定\(l_i,r_i(1 \le l_i,r_i \le n)\)，要你找出所有相等元素对\(a_x\)和\(a_y(l_i \le x,y \le r_i)\)中，绝对值\(|x-y|\)的最小值。
Solution
考虑三个相等的元素\(a_x,a_y,a_z(x < y < z)\)，对于一个区间包含这三个元素的询问，我们只需要考虑\(|x-y|\)和\(|z-y|\)的大小，可以直接舍弃掉\(|z-x|\)，由此我们可以注意到，只需要关注相等元素那些相邻的元素对即可。那么基于此，整个序列中最多只会有\(n-1\)的元素对需要考虑。
那么如何维护这写元素对对应的线段长度来回答询问呢？
一个朴素的想法是把询问离线下来，按左端点排序，扫描线处理。线段长度则这样维护，把每个点作为左端点时的对应的最短线段长度记录下来，然后整体丢到一个数据结构里面。扫描的时候，把扫过点对应的信息从数据结构里删除，回答询问的时候从集合里查询区间最小值。显然，可以用线段树来实现它。
剩下的只需要预处理出各个元素作为左端点时对应的右端点，再全部插入线段树中即可。
时间复杂度\(O(nlog^2n)\)，预处理有一个离散化，因此是双\(log\)的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N=5e5+10;
struct node{int l,r;int w;
}tr[N<<2];void build(int u,int l,int r){tr[u]={l,r,(int)1e9};if(l==r) return;int m=(l+r)>>1;build(u<<1,l,m);build(u<<1|1,m+1,r);
}void modify(int u,int l,int r,int k){if(l<=tr[u].l&&tr[u].r<=r){tr[u].w=k;return;}int m=(tr[u].l+tr[u].r)>>1;if(l<=m) modify(u<<1,l,r,k);if(r>m) modify(u<<1|1,l,r,k);tr[u].w=min(tr[u<<1].w,tr[u<<1|1].w);
}int query(int u,int l,int r){if(l<=tr[u].l&&tr[u].r<=r){return tr[u].w;}int m=(tr[u].l+tr[u].r)>>1;int res=1e9;if(l<=m) res=min(res,query(u<<1,l,r));if(r>m) res=min(res,query(u<<1|1,l,r));return res;
}int main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];vector<array<int,3>> q(m);for(int i=0;i<m;i++){cin>>q[i][0]>>q[i][1];q[i][2]=i;}sort(q.begin(),q.end());map<int,int> p;vector<int> nxt(n,-1);build(1,1,n);for(int i=n-1;~i;i--){if(p.count(a[i])){nxt[i]=p[a[i]];modify(1,nxt[i]+1,nxt[i]+1,nxt[i]-i);}p[a[i]]=i;}vector<int> ans(m);for(int i=0,j=0;i<n;i++){while(j<m&&q[j][0]==i+1){ans[q[j][2]]=query(1,q[j][0],q[j][1]);j++;}if(nxt[i]!=-1) modify(1,nxt[i]+1,nxt[i]+1,1e9);}for(int i=0;i<m;i++){if(ans[i]==1e9) ans[i]=-1;cout<<ans[i]<<'\n';}return 0;
}
