[Luogu] 洛谷 CF522D 题解【Closest Equals】

实际上是为了不让后人没一篇优秀的题解看

进入正题

翻译 实际上是我懒得打了

emmmm，怎么这么多实际上QAQ？

不管啦，看题，我们将相同的数作为一个区间存下来

将两个的坐标分别作为区间的左右端点

然后我们发现

如果有一个区间包含了另一个区间，那么！！！

就可以删掉那个较大的区间，是不是很神奇！是不是！是不是！

咳咳，言归正传，那么我们们在边读边做时就会自动的将区间按左端点从小到大排序

由上可知，右端点也是有序的

在每次询问时，我们可以二分一个查找，找到可以得出答案的范围

在其中找最小的区间长度，就可以啦~~~

上面的一步可以用RMQ哦QAQ

注意：当我们找出的l和r有l>r时，就输出-1啦

丢代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[500001],d[500001],cnt;
int logg[500001];
int f[500001][40];
int l[500001],r[500001];
map <int,int> mp;//第一个是原值，第二个是原值的位置
inline int min(int a,int b)
{
    return a<b? a:b;
}
inline int read()
{
    int x=0,w=0;char ch=0;
    while(!(ch>=‘0‘&&ch<=‘9‘))
    {
        if(ch==‘-‘) w=1;
        ch=getchar();
    }
    while(ch>=‘0‘&&ch<=‘9‘)
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}
int main(){
    n=read();
    m=read();
    for(register int i=1;i<=n;++i)
    {
        a[i]=read();
        if(mp.count(a[i]))
        {
            int j=mp.find(a[i])->second;
            mp[a[i]]=i;
            if(!cnt) l[++cnt]=j,r[cnt]=i,d[cnt]=i-j;
            else if(l[cnt]>=j) continue;
            else l[++cnt]=j,r[cnt]=i,d[cnt]=i-j;
        }
        else mp.insert(make_pair(a[i],i));
    }
    logg[0]=-1;
    for(register int i=1;i<=cnt;++i)
      f[i][0]=d[i],logg[i]=logg[i>>1]+1;
    for(register int j=1;(1<<j)<=cnt;++j)
      for(register int i=1;i+(1<<j)-1<=cnt;++i)
        f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
    for(register int i=1;i<=m;++i)
    {
        int x,y;
        x=read();
        y=read();
        x=lower_bound(l+1,l+cnt+1,x)-l;
        y=upper_bound(r+1,r+cnt+1,y)-r-1;
        if(y<x) {cout<<-1<<endl; continue;}
        int s=logg[y-x+1];
        printf("%d\n",min(f[x][s],f[y-(1<<s)+1][s]));
    }
}