Codeforces 522D Closest Equals【思维+线段树+离线查询】好题~

D. Closest Equals time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output

You are given sequence a₁, a₂, ..., a_n and m queries l_j, r_j (1 ≤ l_j ≤ r_j ≤ n). For each query you need to print the minimum distance between such pair of elements a_x and a_y (x ≠ y), that:

both indexes of the elements lie within range [l_j, r_j], that is, l_j ≤ x, y ≤ r_j; the values of the elements are equal, that is a_x = a_y.

The text above understands distance as |x - y|.

Input

The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·10⁵) — the length of the sequence and the number of queries, correspondingly.

The second line contains the sequence of integers a₁, a₂, ..., a_n ( - 10⁹ ≤ a_i ≤ 10⁹).

Next m lines contain the queries, one per line. Each query is given by a pair of numbers l_j, r_j (1 ≤ l_j ≤ r_j ≤ n) — the indexes of the query range limits.

Output

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.

Examples Input 5 3 1 1 2 3 2 1 5 2 4 3 5 Output 1 -1 2 Input 6 5 1 2 1 3 2 3 4 6 1 3 2 5 2 4 1 6 Output 2 2 3 -1 2

题目大意：

给你N个数，m个查询，每个查询【l，r】表示询问在区间【l，r】内，最近的一对值相等的数的距离。

思路：

1、设定pre【i】=x.表示a【i】==a【x】&&x是距离i最近的之前的位子。

那么问题就转化成为 ，查询一段区间【l，r】内，i-pre【i】的最小值。

区间查询最小值，线段树可以O（logn）查询；

2、但是因为前后数是否存在的约束性，我们在线查询的时间复杂度是非常高的，因为我们要不断的维护一些数是否存在。

那么我们不妨离线查询。

将所有查询按照l从小到大排序。

那么我们将相关【1，i】的查询全部处理完成之后，那么我们就可以去掉a【1】这个数，并且使得pre【i】==1的那个pre【i】置为inf（就相当于删除掉了位子1上边这个数）.

而且能够保证之后的查询中，a【1】不对之后的查询有影响。

那么过程维护一下即可。

时间复杂度O（nlogn）；

Ac代码：

#include<stdio.h> #include<string.h> #include<map> #include<algorithm> using namespace std; struct node { int l,r,pos; }p[1160000]; #define lson l,m,rt*2 #define rson m+1,r,rt*2+1 int tree[1000050*8]; int a[1160000]; int pre[1160000]; int ans[1160000]; int marry[1160000]; 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]); } int Query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return tree[rt]; } else { int m=(l+r)>>1; int ans=0x3f3f3f3f; if(L<=m) { ans=min(Query(L,R,lson),ans); } if(m<R) { ans=min(Query(L,R,rson),ans); } return ans; } } void build( int l ,int r , int rt ) { if( l == r ) { tree[rt]=0x3f3f3f3f; return ; } else { int m = (l+r)>>1 ; build(lson) ; build(rson) ; pushup(rt) ; } } void update(int p,int c,int l,int r,int rt)//p阵营c数据. { if(l==r) { tree[rt]=c; } else { int m=(l+r)>>1; if(p<=m) update(p,c,lson); else update(p,c,rson); pushup(rt); } } int main() { int n,q; while(~scanf("%d%d",&n,&q)) { map<int ,int >s; memset(marry,-1,sizeof(marry)); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++) { if(i==1) { pre[i]=0x3f3f3f3f; } else { if(s[a[i]]==0) { pre[i]=0x3f3f3f3f; } else { pre[i]=s[a[i]]; marry[s[a[i]]]=i; } } s[a[i]]=i; if(pre[i]==0x3f3f3f3f)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); 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(marry[j],0x3f3f3f3f,1,n,1); now++; } } ans[p[i].pos]=Query(1,p[i].r,1,n,1); if(ans[p[i].pos]==0x3f3f3f3f)ans[p[i].pos]=-1; } for(int i=0;i<q;i++)printf("%d\n",ans[i]); } }