Codeforces VK Cup 2015

D. Closest Equals

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

https://codeforces.com/problemset/problem/522/D

Description

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

Sample Input

Sample Output

1
-1
2

HINT

题意

查询区间相同数的最小距离

题解：

首先对于每个数x我们只需要知道距离最近的x的位置即可，想一想为什么。

具体做法：

１．先离散，然后搞一个nex[]，nex[i]表示位置i右边和它权值相等且最近的位置。

２．这样对于每个询问(l,r),只有当i和nex[i]都在(l,r)内才能计算贡献。

３．看起来很麻烦其实我们可以离线做，将询问按左端点从小到大排序，

　　先将(1,n)赋值成INF(一个很大的数),

　　当扫到区间(l,r)时，对于i(l<=i<=r),我们将nex[i]位置赋值为nex[i]-i，然后直接求(l,r)的最小值即可。

　　注意当i<l后记得将nex[i]重新赋值为INF。

4.推荐用树状数组做一下《HH的项链》，思想有异曲同工之妙。

Debug：

读入优化忘记处理负数，一直wa在19个点，真是悲伤，数据太水了吧，前面的负数是怎过的？

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1000050
 4 #define INF 12345678
 5 #define LL long long 
 6 LL n,m,cnt,kth[N],a[N],nex[N],last[N],ans[N];
 7 struct Query
 8 {
 9   LL l,r,id;
10   bool operator <(const Query&b)const
11   {return l<b.l;}
12 }q[N];
13 struct Tree{LL l,r,min;}tr[N<<2];
14 template<typename T>void read(T&x)
15 {
16   LL k=0;char c=getchar();
17   x=0;
18   while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
19   if(c==EOF)exit(0);
20   while(isdigit(c))x=x*10+c-'0',c=getchar();
21 }
22 void bt(LL x,LL l,LL r)
23 {
24   tr[x]=Tree{l,r,INF};
25   if(l==r)return;
26   LL mid=(l+r)>>1;
27   bt(x<<1,l,mid);
28   bt(x<<1|1,mid+1,r);
29 }
30 void update(LL x,LL p,LL tt)
31 {
32   if (p<=tr[x].l&&tr[x].r<=p)
33     {
34       tr[x].min=tt;
35       return;
36     }
37   LL mid=(tr[x].l+tr[x].r)>>1;
38   if(p<=mid)update(x<<1,p,tt);
39   if (mid<p)update(x<<1|1,p,tt);
40   tr[x].min=min(tr[x<<1].min,tr[x<<1|1].min);
41 }
42 LL query(LL x,LL l,LL r)
43 {
44   if(l<=tr[x].l&&tr[x].r<=r)
45     return tr[x].min;
46   LL mid=(tr[x].l+tr[x].r)>>1,ans=INF;
47   if(l<=mid)ans=query(x<<1,l,r);
48   if(mid<r)ans=min(ans,query(x<<1|1,l,r));
49   return ans;
50 }
51 int main()
52 {
53 #ifndef ONLINE_JUDGE
54   freopen("aa.in","r",stdin);
55 #endif
56   read(n); read(m);
57   bt(1,1,n);
58   for(LL i=1;i<=n;i++)read(a[i]),kth[i]=a[i];
59   sort(kth+1,kth+n+1);
60   cnt=unique(kth+1,kth+n+1)-kth-1;
61   for(LL i=1;i<=n;i++)a[i]=lower_bound(kth+1,kth+cnt+1,a[i])-kth;
62   for(LL i=1;i<=n;i++)
63     {
64       if (last[a[i]])nex[last[a[i]]]=i;
65       last[a[i]]=i;
66     }
67   for(LL i=1;i<=m;i++)
68     {
69       q[i].id=i;
70       read(q[i].l); read(q[i].r);
71     }
72   sort(q+1,q+m+1);
73   LL l=q[1].l,r=q[1].l-1;
74   for(LL i=1;i<=m;i++)
75     {
76       for(LL j=l;j<=q[i].l-1;j++)
77     if (nex[j]>0)update(1,nex[j],INF);
78       for(LL j=r+1;j<=q[i].r;j++)
79     if (nex[j]>0)update(1,nex[j],nex[j]-j);
80       ans[q[i].id]=query(1,q[i].l,q[i].r);
81       if(ans[q[i].id]==INF)ans[q[i].id]=-1;
82       l=q[i].l;
83       r=max(r,q[i].r);
84     }
85   for(LL i=1;i<=m;i++)
86     printf("%lld
",ans[i]);
87 }
88

View Code