RT，我本来只是想测试一下我对题意理解是否有误，交了一发暴力，准备待会再上线段树等优化，结果谁知道直接过了。

#include<bits/stdc++.h>
using namespace std;
int n,q,m;
vector<int> a[1000006];
long long lastans=0;
long long ansc[1000006];int ansx[1000006];

int fa[1000006];
int find(int x)
{
	if(!fa[x]) return x;
	return fa[x]=find(fa[x]);
}
long long L[1000006],R[1000006];
inline void init()
{
	memset(fa,-1,sizeof fa),memset(ansc,-1,sizeof ansc),memset(ansx,-1,sizeof ansx);
	int cnt=0;long long ans=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<a[i].size();j++)
		{
			int x=a[i][j];fa[x]=0,L[x]=R[x]=x;cnt++,ans++;
			if(~fa[x-1]) {int y=find(x-1);x=find(x);ans-=(R[x]-L[x]+1)*(R[x]-L[x]+1),ans-=(R[y]-L[y]+1)*(R[y]-L[y]+1),R[y]=max(R[y],R[x]),cnt--,fa[x]=y,ans+=(R[y]-L[y]+1)*(R[y]-L[y]+1);}
			if(~fa[x+1]) {int y=find(x+1);x=find(x);ans-=(R[x]-L[x]+1)*(R[x]-L[x]+1),ans-=(R[y]-L[y]+1)*(R[y]-L[y]+1),L[y]=min(L[y],L[x]),cnt--,fa[x]=y,ans+=(R[y]-L[y]+1)*(R[y]-L[y]+1);}
		}//cout<<cnt<<' '<<ans<<'\n';
		ans*ansx[cnt]>=ansc[cnt]*i||ansx[cnt]==-1? (ansc[cnt]=ans,ansx[cnt]=i):0;
	}//for(int i=1;i<=n;i++) cout<<ansc[i]<<' '; cout<<'\n';
	//for(int i=1;i<=n;i++) cout<<ansx[i]<<' '; cout<<'\n';
}

inline void solve()
{
	long long a,b,x,y,l,r;
	cin>>a>>b>>x>>y;
	l=(a*lastans+x-1)%n+1,r=(b*lastans+y-1)%n+1;if(l>r)swap(l,r);
	long long c=-1;x=-1;
	for(int i=l;i<=r;i++)
	{
		if(ansc[i]==-1) continue;
		if(x==-1||ansc[i]*x>c*ansx[i]||(ansc[i]*x==c*ansx[i]&&ansx[i]>x)) c=ansc[i],x=ansx[i];
	}
	cout<<c<<' '<<x<<'\n';
	cout<<l<<' '<<r<<' '<<lastans<<'\n';
	lastans=c*x%n;
}

int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>q;int aa;
	for(int i=1;i<=n;i++) cin>>aa,a[aa].push_back(i),m=max(m,aa);
	init();
	
	while(q--)
	{
		solve();
	}return 0;
}

甚至连$O2$都不需要开……

评测记录