分块做法 WA+TLE 0pts 求调（玄1关）

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=sqrt(N)+5;
int n,m,a[N],mp[N];
void discrete(){
	int b[N];
	map<int,int>pm;
	for(int i=1;i<=n;i++)b[i]=a[i];
	sort(b+1,b+n+1),mp[1]=b[1],pm[b[1]]=1,m=1;
	for(int i=1,j=1;i<=n;i++)
		if(b[i]!=b[i-1]&&i!=1)
			j++,mp[j]=b[i],pm[b[i]]=j,m=j;
	for(int i=1;i<=n;i++)
		a[i]=pm[a[i]];
}
struct decompose{
	int x[N],f[N],p[M][M],s[M][N],baselen,cnt;
	int blockl(int x){
		return (x-1)*baselen+1;
	}
	int blockr(int x){
		return min(x*baselen,n);
	}
	void build(){
		baselen=sqrt(n);
		for(int i=1;i<=n;i++){
			if(i%baselen==1)
				cnt++;
			f[i]=cnt,x[i]=a[i],s[cnt][x[i]]++;
		}
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=m;j++)
				s[i][j]+=s[i-1][j];
		for(int i=1;i<=cnt;i++)
			for(int j=i;j<=cnt;j++){
				p[i][j]=p[i-1][j];
				for(int k=max(1,blockl(j-1));k<=blockr(j);k++)
					if(s[j][x[k]]-s[i-1][x[k]]>s[j][p[i][j]]-s[i-1][p[i][j]])
						p[i][j]=x[k];
			}	
	}
	int query(int l,int r){
		int b[N]={0},ans=p[f[l]][f[r]];
		if(f[l]==f[r]){
			for(int i=l;i<=r;i++)
				b[x[i]]++;
			for(int i=l;i<=r;i++)
				if(b[x[i]]>b[ans]||b[x[i]]==b[ans]&&x[i]<ans)
					ans=x[i];
			return ans;
		}
		for(int i=l;f[i]==f[l];i++)
			b[x[i]]++;
		for(int i=r;f[i]==f[r];i--)
			b[x[i]]++;
		for(int i=l;f[i]==f[l];i++){
			int now=b[x[i]]+max(0,s[f[r]-1][x[i]]-s[f[l]][x[i]]),
				lst=b[ans]+max(0,s[f[r]-1][ans]-s[f[l]][ans]);
			if(now>lst||now==lst&&x[i]<ans)
				ans=x[i];
		}	
		for(int i=r;f[i]==f[r];i--){
			int now=b[x[i]]+max(0,s[f[r]-1][x[i]]-s[f[l]][x[i]]),
				lst=b[ans]+max(0,s[f[r]-1][ans]-s[f[l]][ans]);
			if(now>lst||now==lst&&x[i]<ans)
				ans=x[i];
		}
		return ans;
	}
}d;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	discrete();
	d.build();
	for(int i=0,l,r;i<n;i++)
		cin>>l>>r,cout<<mp[d.query(l,r)]<<"\n";
	return 0;
}