题目
分析
回滚莫队/莫队+根号分治/线段树。
这道题和回滚莫队板题维护的信息正好相反，显然也是可以回滚莫队的。
但是会被卡，但是发现这个题目求的东西和区间数颜色的套路很像，于是可以考虑线段树/树状数组。
于是我们考虑离线询问，把询问挂到右端点上，然后就是查询当前的区间最小值即可。
注意这里的修改是：对于 (pre[i]) 来说，如果出现了 (i) ，那么把位置 (pre[i]) 更新成 (i-pre[i])。
时间复杂度 (O(nlogn))
代码
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=5e5+5,INF=2e9+7;
int n,m,a[N],b[N],pre[N],pos[N],Min[N<<2],res[N];
struct Que{int l,id;};
vector<Que> Q[N];
void Modify(int p,int l,int r,int x,int v){
if(l==r) return Min[p]=v,void();
int mid=(l+r)>>1;
if(x<=mid) Modify(p<<1,l,mid,x,v);
else Modify(p<<1|1,mid+1,r,x,v);
Min[p]=min(Min[p<<1],Min[p<<1|1]);
return ;
}
int Query(int p,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r) return Min[p];
int mid=(l+r)>>1,res=INF;
if(ql<=mid) res=min(res,Query(p<<1,l,mid,ql,qr));
if(qr>mid) res=min(res,Query(p<<1|1,mid+1,r,ql,qr));
return res;
}
int main(){
read(n),read(m);
for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
sort(b+1,b+n+1);
int cnt=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b,pre[i]=pos[a[i]],pos[a[i]]=i;
for(int i=1,l,r;i<=m;i++) read(l),read(r),Q[r].push_back((Que){l,i});
for(int i=1;i<=4*n;i++) Min[i]=INF;
for(int i=1;i<=n;i++){
if(pre[i]) Modify(1,1,n,pre[i],i-pre[i]);
for(int j=0;j<Q[i].size();j++) res[Q[i][j].id]=Query(1,1,n,Q[i][j].l,i);
}
for(int i=1;i<=m;i++) write((res[i]==INF)?-1:res[i]),putchar('
');
return 0;
}