You are given sequence a1, a2, ..., an and m queries lj, rj (1 ≤ lj ≤ rj ≤ n). For each query you need to print the minimum distance between such pair of elements ax and ay (x ≠ y), that:
- both indexes of the elements lie within range [lj, rj], that is, lj ≤ x, y ≤ rj;
- the values of the elements are equal, that is ax = ay.
The text above understands distance as |x - y|.
The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·105) — the length of the sequence and the number of queries, correspondingly.
The second line contains the sequence of integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109).
Next m lines contain the queries, one per line. Each query is given by a pair of numbers lj, rj (1 ≤ lj ≤ rj ≤ n) — the indexes of the query range limits.
Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.
5 3
1 1 2 3 2
1 5
2 4
3 5
1
-1
2
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6
2
2
3
-1
2
题目链接
题意
给你n个数,m个查询,每次查询区间[l,r]中两个相同元素最近的距离的最小值。
分析
1.设pre[i]为a[i]==a[pre[i]]且pre[i]是在i之前的距离最近的位置。那么问题就变成查询区间中最小的i-pre[i]的值,也就是区间最小值,可以用线段树处理。
2.但是,当某个点不在此区间内时,我们是不考虑的。由于这题是没有修改的,可以想到离线处理。将查询区间按左端点排序,假设当前查询的区间到了[l,r],
那么在下标l之前的所以元素都不能考虑入内,所以我们需要消除它们对其后的最近点的影响,即使得pre[i]==x的那个pre[i]置为inf。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include <queue> #include <vector> #include<bitset> #include<map> using namespace std; typedef long long LL; const int maxn = 5e5+5; const int mod = 772002+233; typedef pair<int,int> pii; #define X first #define Y second #define pb push_back #define mp make_pair #define ms(a,b) memset(a,b,sizeof(a)) const int inf = 0x3f3f3f3f; #define lson l,m,2*rt #define rson m+1,r,2*rt+1 struct node{ int l,r,pos; }p[maxn]; int tree[maxn*8],a[maxn],pre[maxn],ans[maxn],data[maxn]; int cmp(node a,node b){ return a.l<b.l; } void pushup(int rt){ tree[rt]=min(tree[rt<<1],tree[rt<<1|1]); } //L,R为查询区间 int query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R){ return tree[rt]; } int m=(r+l)>>1; int res=inf; if(L<=m){ res=min(query(L,R,lson),res); } if(m<R){ res=min(query(L,R,rson),res); } return res; } void build(int l,int r,int rt){ if(l==r){ tree[rt]=inf; return; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int pos,int da,int l,int r,int rt){ if(l==r){ tree[rt]=da; return; } int m=(l+r)>>1; if(pos<=m) update(pos,da,lson); else update(pos,da,rson); pushup(rt); } int main(){ int n,q; scanf("%d%d",&n,&q); // build(1,n,1); for(int i=1;i<=n;i++) scanf("%d",&a[i]); ms(data,-1); ms(tree,inf); map<int,int> ma; //ma[i]存储i所在的位置 for(int i=1;i<=n;i++){ if(i==1) pre[i]=inf; else{ if(ma[a[i]]==0){ pre[i]=inf; }else{ pre[i]=ma[a[i]]; data[ma[a[i]]]=i; //data[i]表示i位置处的数后面最近的数的下标,用作离线维护 } } ma[a[i]]=i; if(pre[i]==inf) update(i,pre[i],1,n,1); else update(i,i-pre[i],1,n,1); } for(int i=0;i<q;i++){ scanf("%d%d",&p[i].l,&p[i].r); p[i].pos=i; } sort(p,p+q,cmp); // for(int i=1;i<=n;i++) cout<<data[i]<<" "; // puts(""); int now=1; for(int i=0;i<q;i++){ if(p[i].l>now){ for(int j=now;j<p[i].l;j++){ update(data[j],inf,1,n,1); now++; } } ans[p[i].pos]=query(1,p[i].r,1,n,1); if(ans[p[i].pos]==inf) ans[p[i].pos]=-1; } for(int i=0;i<q;i++) cout<<ans[i]<<endl; return 0; }