16pts回滚莫队求助
查看原帖
16pts回滚莫队求助
494601
gcx12012楼主2023/10/19 21:42

考虑到了几乎所有细节,但是还是错了,能帮忙看看吗

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define N 200010
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rof(i,a,b) for(int i=a;i>=b;i--)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pb push_back
#define mk make_pair
#define pque priority_queue

using namespace std;
int a[N],b[N],ans[N];
int L[N],R[N],cnt=0,pos[N];
int n,q,bl;
int s[N],t[N],s2[N],t2[N];
struct node{
	int l,r,id;
}c[N];

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool cmp(node x,node y){
	if(pos[x.l]==pos[y.l]) return x.r<y.r;
	return pos[x.l]<pos[y.l];
}

int main()
{
    n=read();
    For(i,1,n) a[i]=b[i]=read();
    sort(b+1,b+n+1);
    int tot=unique(b+1,b+n+1)-b-1;
    For(i,1,n) a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    q=read();
    For(i,1,q) c[i].l=read(),c[i].r=read(),c[i].id=i;
    bl=n/(int)sqrt(q);
    if(!bl) bl=1;
    while(R[cnt]+bl<=n){
    	L[cnt+1]=R[cnt]+1;
    	R[cnt+1]=R[cnt]+bl;
    	cnt++;
	}
	if(R[cnt]<n){
		L[cnt+1]=R[cnt]+1;
    	R[cnt+1]=n;
    	cnt++;
	}
	For(i,1,cnt){
		//cout<<L[i]<<' '<<R[i]<<endl;
		For(j,L[i],R[i]){
			pos[j]=i;
		}
	}
    sort(c+1,c+q+1,cmp);
    int l=1,r=n,__l,Ans=0,lst=0;
    For(i,1,q){
    	//cout<<c[i].l<<' '<<c[i].r<<endl;
    	if(pos[c[i].l]==pos[c[i].r]){
    		For(j,c[i].l,c[i].r){
    			if(!s2[a[j]]) s2[a[j]]=j;
    			else ans[c[i].id]=max(ans[c[i].id],j-s2[a[j]]);
			}
			For(j,c[i].l,c[i].r) s2[a[j]]=0;
			continue;
		}
		if(pos[c[i].l]!=lst){
			lst=pos[c[i].l];
			r=n;
			while(r>R[pos[c[i].l]]) s[a[r]]=t[a[r]]=0,r--;
			while(l<=R[pos[c[i].l]]) s[a[l]]=t[a[l]]=0,l++;
			Ans=0;
		}
		while(r<c[i].r){
			r++;
			if(!s[a[r]]) s[a[r]]=t[a[r]]=r;
			else t[a[r]]=r,Ans=max(Ans,t[a[r]]-s[a[r]]);
		}
		__l=l;
		int tmp=Ans;
		while(__l>c[i].l){
			__l--;
			if(!t[a[__l]]) t2[a[__l]]=__l;
			if(t[a[__l]]) tmp=max(tmp,t[a[__l]]-__l);
			else tmp=max(tmp,t2[a[__l]]-__l);
		}
		ans[c[i].id]=tmp;
		while(__l<l) t2[a[__l]]=0,__l++;
	}
	For(i,1,q) printf("%d\n",ans[i]);
    return 0;
}
/*
10
1 2 3 4 5 6 7 8 9 1
3
1 9
1 10
2 10
*/
2023/10/19 21:42
加载中...