社区讨论

萌新刚学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 条回复,欢迎继续交流。

正在加载回复...