一个小小的疑问
查看原帖
一个小小的疑问
280999
_fairytale_楼主2023/1/16 23:47

AC CODE:

#include<bits/stdc++.h>
using namespace std;
#define re register
#define int long long
const int maxn=1e6+5;
inline int read() {
	int sum=0,sign=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-')sign=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum*sign;
}
int n,m;
int a[maxn];
int R[maxn];
int st[maxn],ed[maxn],ed2[maxn];
struct query {
	int l,r,id;
} q[maxn];
int block;
int kuai[maxn];
bool cmp(query x,query y) {
	if(kuai[x.l]==kuai[y.l]) return x.r<y.r;
	return kuai[x.l]<kuai[y.l];
}
int ans[maxn];
int answer,bloc;
int b[maxn];
inline int max(int x,int y) {
	return x>y?x:y;
}
void move() {
	int le=0,ri=0,bloc=0;
	for(int i=1; i<=m; ++i) {
		if(kuai[q[i].l]==kuai[q[i].r]) {
			int res=0;
			for(int j=q[i].l; j<=q[i].r; ++j) {
				st[a[j]]=0;
			}
			for(int j=q[i].l; j<=q[i].r; ++j) {
				if(!st[a[j]])st[a[j]]=j;
				res=max(res,j-st[a[j]]);
			}
			for(int j=q[i].l; j<=q[i].r; ++j) {
				st[a[j]]=0;
			}
			ans[q[i].id]=res;
			continue;
		}//暴力
		int now=kuai[q[i].l];
		//cout<<now<<'\n';
		if(now!=bloc) {
			answer=0;
			for(int j=le; j<=ri; ++j) {
				st[a[j]]=ed[a[j]]=0;
			}
			le=R[now];ri=le-1;
			bloc=now;
		}
		while(ri<q[i].r) {
			ri++;
			if(!st[a[ri]])st[a[ri]]=ri;
			ed[a[ri]]=ri;
			answer=max(answer,ri-st[a[ri]]);
		}
		int p=le;
		int tmp2=0;
		while(p>q[i].l) {
			p--;
			if(!ed2[a[p]])ed2[a[p]]=p;
			//answer=max(answer,max(ed[a[p]],ed2[a[p]])-p);
            tmp2=max(tmp2,max(ed[a[p]],ed2[a[p]])-p);
		}
		while(p<le) {
			ed2[a[p]]=0;
			p++;
		}
		ans[q[i].id]=max(answer,tmp2);
	}
}
signed main() {
	n=read();
	block=sqrt(n);
	for(re int i=1; i<=n; ++i) {
		b[i]=read();
		a[i]=b[i];
		kuai[i]=(i-1)/block +1;
	}
	for(int i=1; i<=kuai[n]; i++)R[i]=(i==kuai[n])?n:block*i;
	sort(b+1,b+n+1);
	int len=unique(b+1,b+n+1)-b-1;
	for(int i=1; i<=n; ++i) {
		a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	}
	/*for(int i=1; i<=n; ++i) {
		cout<<a[i]<<" ";
	}
	cout<<'\n';*/
	m=read();
	for(int i=1; i<=m; ++i) {
		q[i].id=i;
		q[i].l=read(),q[i].r=read();
		if(q[i].l>q[i].r) {
			swap(q[i].l,q[i].r);
		}
	}
	sort(q+1,q+m+1,cmp);
	move();
	for(int i=1; i<=m; ++i) {
		cout<<ans[i]<<'\n';
	}
	return 0;
}

为什么第80行的tmp2换成answer就会WA成10pts

2023/1/16 23:47
加载中...