题意：一个数列 aia _i，多次询问，每次询问一个区间 [l,r][l,r]，求区间内相同的两个数的最近距离。

一道比较难的题。

这道题要用线段树来做，还是算贡献的思想。要求 ll 到 rr 的区间内两个相同的数的最近距离，我们可以建立两个结构体，一个存储数列中所有相同的两个数的编号，另一个则存储问题的区间。

我们先可以将两个结构体按照左边的编号从小到大排序。接着统计答案，倒着枚举每一个问题区间，对于每一个区间，再拿一个指针倒着搜编号区间。如果问题区间的左端点小于等于编号区间的左边那个数的编号，那么如果编号区间的右端点在问题区间内即可统计答案。

这时我们就需要线段树来辅助了。线段树要满足单点修改，区间查询最小值的操作。对于一个编号区间 [l,r][l,r]，如果要把它的贡献算上，就把线段树中下标为 rr 的点的值修改为 r−l+1r-l+1，即这个区间的最小长度，便于查询最小值。对于每一个问题区间 [L,R][L,R] 的答案，就是区间查询 [1,R][1,R] 的最小值即可。为什么是 [1,R][1,R] 呢？

先看看这一段的代码：

for(int i=m;i>=1;i--)
{
	while(j>=1&&q[i].l<=s[j].l)
	{
		update(s[j].r,s[j].r-s[j].l,1,n,1);
		j--;
	}
	ans[q[i].id]=query(1,q[i].r,1,n,1);
	if(ans[q[i].id]==INF)
		ans[q[i].id]=-1;
}

因为我们是倒着搜的(由于排序，左端点从大到小)，所以之前已经算了贡献(即已单点修改)的编号区间，肯定它的左端点比之后所有的问题区间的左端点都要大，因此它本来就要被算进答案内，所以直接从 11 开始统计即可。

最后记得离散化即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int maxn=200010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,m,last[maxn],b[maxn];
int minn[maxn],cnt,tot,ans[maxn];
struct feature
{
	long long x;
	int id;
}a[maxn];
struct node
{
	int l;
	int r;
}s[maxn];
struct question
{
	int l;
	int r;
	int id;
}q[maxn];
int cmpa(feature a,feature b)
{
	return a.x<b.x;
}
int cmps(node a,node b)
{
	return a.l<b.l;
}
int cmpq(question a,question b)
{
	return a.l<b.l;
}
void pushup(int rt)
{
	minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		minn[rt]=INF;
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}
void update(int x,int val,int l,int r,int rt)
{
	if(l==r)
	{
		minn[rt]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		update(x,val,lson);
	else
		update(x,val,rson);
	pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
	int ans=INF;
	if(L<=l&&r<=R)
		return minn[rt];
	int mid=(l+r)>>1;
	if(L<=mid)
		ans=min(ans,query(L,R,lson));
	if(R>mid)
		ans=min(ans,query(L,R,rson));
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i].x);
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmpa);
	b[a[1].id]=++cnt;
	for(int i=2;i<=n;i++)
	{
		if(a[i].x!=a[i-1].x)
			b[a[i].id]=++cnt;
		else
			b[a[i].id]=cnt;
	}//离散化
	for(int i=1;i<=n;i++)
	{
		if(!last[b[i]])
			last[b[i]]=i;
		else
		{
			s[++tot].l=last[b[i]];
			s[tot].r=i;
			last[b[i]]=i;
		}
	}//s结构体存储编号区间
	sort(s+1,s+tot+1,cmps);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmpq);
	build(1,n,1);
	int j=tot;
	for(int i=m;i>=1;i--)
	{
		while(j>=1&&q[i].l<=s[j].l)
		{
			update(s[j].r,s[j].r-s[j].l,1,n,1);
			j--;
		}
		ans[q[i].id]=query(1,q[i].r,1,n,1);
		if(ans[q[i].id]==INF)
			ans[q[i].id]=-1;
	}//统计答案
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}