实际上是为了不让后人没一篇优秀的题解看
进入正题
翻译 https://www.luogu.org/discuss/show/50529 实际上是我懒得打了
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]));
- }
- }
来源: http://www.bubuko.com/infodetail-2807729.html