自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 22:06:10，当前版本为作者最后更新于2021-09-21 12:18:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目不带修，故 $x$ 的取值只有 $O(n)$ 种。考虑预处理出所有 $x$ 对应的答案。从小到大枚举 $x$，使用并查集维护连续段的数量，长度，以及长度的平方和。这样会得到 $O(n)$ 个三元组 $(cnt,y,x)$ 表示所选数为 $x$ 时有 $cnt$ 个连续段，其长度的平方和为 $y$，对应的答案为 $\frac{y}{x}$。把所有 $cnt$ 相同的三元组放在一起按答案取 max，问题转为 rmq。

使用普通的 st 表或线段树容易被卡空间。这里采用分块+ st 表的方式，每 log 个点分为一块，整块之间用 st 表维护，零散点暴力。时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

代码如下（点个赞再走吧QAQ，万分感谢！）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#define pb push_back
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define db double
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') fh=-1; ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*fh;}
inline void out(int *a,int n){fo(i,1,n) printf("%d ",*(a+i));puts("");}

const int N=1e6+5;
int a[N],od[N],n,siz[N],fa[N],cnt,vis[N],T,lg,tot,bel[N];
ll ans,lst;
struct frac{
	ll fz;
	int fm;
	frac(){fz=0,fm=1;}
	frac(ll x,int y){fz=x,fm=y;} 
	bool operator<(const frac&x)const{return fz*x.fm<fm*x.fz;} 
}A[N],st[N/19+5][20],Ans;

int fin(int x){return fa[x]==x?x:fa[x]=fin(fa[x]);} 
bool cmp(int x,int y){return a[x]<a[y];} 
inline void merge(int x,int y){
	int fx=fin(x),fy=fin(y);
	if(fx==fy) return;
	if(siz[fx]<siz[fy]) fa[fx]=fy,siz[fy]+=siz[fx];
	else fa[fy]=fx,siz[fx]+=siz[fy];
}

void rmq(){
	fo(i,1,n) bel[i]=(i-1)/lg+1,big(st[bel[i]][0],A[i]);
	fo(i,1,lg)
		fo(j,1,tot) st[j][i]=max(st[j][i-1],st[min(j+(1<<i-1),tot)][i-1]);
}

inline frac query(int l,int r){
	int x=log2(r-l+1); 
	return max(st[l][x],st[r-(1<<x)+1][x]);
}

int main(){
	cin>>n>>T;lg=log2(n);tot=(n-1)/lg;
	fo(i,1,n) a[i]=read(),od[i]=i,fa[i]=i,siz[i]=1;
	sort(od+1,od+1+n,cmp);
	fo(i,1,n){
		int R=i;
		while(a[od[R]]==a[od[R+1]]) R++;
		fo(j,i,R){
			int k=od[j];
			ll sum=0;
			vis[k]=1;
			if(vis[k-1]) cnt--,sum+=(ll)siz[fin(k-1)]*siz[fin(k-1)],merge(k-1,k);
			if(vis[k+1]) cnt--,sum+=(ll)siz[fin(k+1)]*siz[fin(k+1)],merge(k+1,k);
			cnt++;
			ans+=(ll)siz[fin(k)]*siz[fin(k)]-sum;
		}
		//cnt:连续段的个数，ans:长度平方和，a[od[i]]:所选数 
		big(A[cnt],frac(ans,a[od[i]]));
		//printf("%d:%lld/%d\n",cnt,ans,a[od[i]]);
		i=R;
	}
	//fo(i,1,n) printf("%d:%lld/%d\n",i,A[i].fz,A[i].fm);
	rmq();
	while(T--){
		int a=read(),b=read(),x=read(),y=read();
		int l=(a*lst+x-1)%n+1,r=(b*lst+y-1)%n+1;
		if(l>r) swap(l,r);
		x=bel[l],y=bel[r];
		Ans=frac();
		if(y-x<=1) fo(i,l,r) big(Ans,A[i]);
		else{
			fo(i,l,lg*bel[l]) big(Ans,A[i]);
			fo(i,lg*(bel[r]-1)+1,r) big(Ans,A[i]);
			big(Ans,query(bel[l]+1,bel[r]-1));
		}
		if(Ans.fz) printf("%lld %d\n",Ans.fz,Ans.fm);
		else puts("-1 -1");
		printf("%d %d %lld\n",l,r,lst);
		if(Ans.fz) lst=Ans.fz*Ans.fm%n;
		else lst=1;
	}
	return 0;
}