社区讨论
萌新刚学OI,求助大佬,卡在第十一个点上过不去
CF522DClosest Equals参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xl7p9
- 此快照首次捕获于
- 2025/11/20 12:28 4 个月前
- 此快照最后确认于
- 2025/11/20 12:28 4 个月前
我是用RMQ+二分做的第十一个点WA
CPP#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.erase(mp.find(a[i]));
mp.insert(make_pair(a[i],i));
if(!cnt) l[++cnt]=j,r[cnt]=i,d[cnt]=abs(i-j);
else if(l[cnt]<=j&&r[cnt]>=i) continue;
else l[++cnt]=j,r[cnt]=i,d[cnt]=abs(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]));
}
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...