求助回滚莫队莫名RE
查看原帖
求助回滚莫队莫名RE
914961
liaoz123楼主2023/1/18 15:00

不知道代码哪里溢出了,中间一大片RE,一头一尾AC,做P7883也是同样的情况。求助!!!!

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,a[N],b[N],s[N],R[N],len,e[N],ee[N],ans[N];
struct node{
	int id,l,r;
}q[N];
bool cmp(node x,node y){
	return b[x.l]==b[y.l]?x.r<y.r:x.l<y.l;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);int aaa=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+aaa+1,a[i])-b;
	len=sqrt(n);
	for(int i=1;i<=n;i++)b[i]=(i-1)/len+1;
	for(int i=1;i<=b[n];i++)R[i]=(i==b[n]?n:i*len);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int l=0,r,maxn=0,ma=0,now=0;
	for(int i=1;i<=m;i++){
		int x=q[i].l,y=q[i].r;
		if(b[x]==b[y]){
			maxn=0;
			for(int j=x;j<=y;j++)s[a[j]]=0;
			for(int j=x;j<=y;j++){
				if(!s[a[j]])s[a[j]]=j;
				maxn=max(maxn,j-s[a[j]]);
			}
			for(int j=x;j<=y;j++)s[a[j]]=0;
			ans[q[i].id]=maxn;continue;
		}
		if(b[x]!=now){
			for(int j=l;j<=r;j++)s[a[j]]=e[a[j]]=0;
			now=b[x];
			l=R[now];
			r=l-1,maxn=0;
		}
		while(r<y){
			if(!s[a[++r]])s[a[r]]=r;
			e[a[r]]=r;maxn=max(maxn,r-s[a[r]]); 
		}
		int ll=l;ma=0;
		while(ll>x){
			ll--;
			if(!ee[a[ll]])ee[a[ll]]=ll;
			ma=max(ma,max(e[a[ll]],ee[a[ll]])-ll);
		}
		while(ll<l)ee[ll]=0,ll++;
		ans[q[i].id]=max(ma,maxn);
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}
2023/1/18 15:00
加载中...