100分求调

#include <bits/stdc++.h>
#define id(num) (((num)-1)/len+1)
using namespace std;
int n,m;
int cnt,len;
int a[200005];
struct node{
	int l,r;
	bool operator<(const node&t)const{
		return r<t.r;
	}
}line[200005];
int cntnum;
map<int,vector<int*>> mp;
map<pair<int,int>,int> ap;
int fl,fr,fans,fle[200005],fri[200005];
int l,r,ans,le[200005],ri[200005];
vector<node> v[500];
int main(){
	ios::sync_with_stdio(0);
	cout.tie(0);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]].push_back(&a[i]);
	cin>>m;
	for(int i=1;i<=m;i++) cin>>line[i].l>>line[i].r;
	for(auto i:mp){
		++cntnum;
		for(int *j:i.second){
			*j=cntnum;
		}
	}
	len=sqrt(n),cnt=(n+len-1)/len;
	for(int i=1;i<=m;i++){
		if(id(line[i].l)==id(line[i].r)){
			ans=0;
			for(int j=line[i].l;j<line[i].r;j++){
				for(int k=line[i].r;k>j;k--){
					if(a[j]==a[k]){
						ans=max(ans,k-j);
						break;
					}
				}
			}
			ap[{line[i].l,line[i].r}]=ans;
			continue;
		}
		v[id(line[i].l)].push_back(line[i]);
	}
	for(int i=1;i<=cnt;i++){
		if(v[i].empty()) continue;
		sort(v[i].begin(),v[i].end());
		fl=min(i*len,n),fr=v[i][0].r,fans=0;
		memset(fle,0,sizeof(fle));memset(fri,0,sizeof(fri));
		for(int j=fl;j<=fr;j++){
			if(fle[a[j]]==0) fle[a[j]]=fri[a[j]]=j;
			else fri[a[j]]=j,fans=max(fans,fri[a[j]]-fle[a[j]]);
		}
		ap[{fl,fr}]=fans;
		for(int j=1;j<v[i].size();j++){
			while(fr<v[i][j].r){
				fr++;
				if(fle[a[fr]]==0) fle[a[fr]]=fri[a[fr]]=fr;
				else fri[a[fr]]=fr,fans=max(fans,fri[a[fr]]-fle[a[fr]]);
			}
			l=fl,r=fr,ans=fans;
			for(int k=1;k<=cntnum;k++) le[k]=fle[k],ri[k]=fri[k];
			while(l>v[i][j].l){
				l--;
				if(le[a[l]]==0) le[a[l]]=ri[a[l]]=l;
				else le[a[l]]=l,ans=max(ans,ri[a[l]]-le[a[l]]);
			}
			ap[{v[i][j].l,v[i][j].r}]=ans;
		}
	}
	for(int i=1;i<=m;i++) cout<<ap[{line[i].l,line[i].r}]<<"\n";
	return 0;
}