C++ 解法, 执行用时: 869ms, 内存消耗: 29672K, 提交时间: 2021-08-13 15:05:58

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int maxn=7e5+100;
typedef long long ll;
const int N=5e3+100;
ll f[N][N];
int n,m;
ll a[maxn],val[maxn];
int belong[maxn];
int block=101;
map<ll,ll>mp;
vector<ll>v[maxn];
int idx=0;
void init(int x){
	vector<ll>cnt(n);
	ll mx=0;
	for(int i=(x-1)*block+1;i<=n;i++){
		cnt[a[i]]++;
		if(1ll*cnt[a[i]]*val[a[i]]>mx){
			mx=1ll*cnt[a[i]]*val[a[i]];
		}
		f[x][belong[i]]=mx;
	}
}
ll query(int l,int r,int x){
	return upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l);
}
ll query(int l,int r){
	ll mx=f[belong[l]+1][belong[r]-1];
	for(int i=l;i<=min(belong[l]*block,r);i++){
		ll t=query(l,r,a[i]);
		if(1ll*t*val[a[i]]>mx){
			mx=1ll*t*val[a[i]];
		}
	}
	if(belong[l]!=belong[r]){
		for(int i=(belong[r]-1)*block+1;i<=r;i++){
			ll t=query(l,r,a[i]);
			if(1ll*t*val[a[i]]>mx){
				mx=t*val[a[i]];
			}
		}
	}
	return mx;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(mp.find(a[i])==mp.end()){
			mp[a[i]]=++idx;	
			val[idx] = a[i];
		}
		a[i]=mp[a[i]];
		v[a[i]].push_back(i);
	}	
	for(int i=1;i<=n;i++){
		belong[i]=(i-1)/block+1;
	}
	for(int i=1;i<=belong[n];i++){
		init(i);
	}
	ll l,r;
	ll ans=0;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&l,&r);
		l=(ans^l)%n+1;
		r=(ans^r)%n+1;
		if(l>r) swap(l,r);	
		ans=query(l,r);
		cout<<ans<<"\n"; 
	}
}