观察到这样一种情况，随着数越来越大，管辖的区间的变化是：先新增一些单点区间，然后相邻的区间合并。
于是我们可以离散化得到元素集$b_i$并更新一波$a_i$，从小到大累加着算“区间长度平方和”$sum[b_i]$。
这里把区间的信息存在两端，每次操作新增的单点区间合并即可。
在这期间，我们可以同时维护区间个数$c$以及$ans[c]$：相同区间个数下，最大的$\frac{sum[b_k]}{b_k}$对应的$b_k$。
然后关于$ans[c]$我们建一棵线段树，每次回答询问即可。注意处理好无解的情况。
注意$a,b,x,y,lastans$这些都是$long\;long$的，而且对$n$取模。
代码（100分）：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<map> #include<set> #define IL inline #define RG register #define _1 first #define _2 second using namespace std; typedef unsigned int UI; typedef long long LL; const int N=1e6; IL int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch==‘-‘) f=-1; for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-‘0‘; return x*f; } int n,t,a[N+3],m,b[N+3]; vector<int>pos[N+3]; //a[pos[a[i]][j]]=a[i] int len[N+3]; //len[pos[i][j]] LL sum[N+3]; //sum[b[i]]=sum(^2) int ans[N+3]; //ans[cnt]=b[i] IL int sol(int x){ int l=1,r=m,mid,ans; while(l<=r){ mid=(l+r)>>1; if(x<=b[mid]){ r=mid-1; ans=mid; } else l=mid+1; } return ans; } IL void pre(){ for(int i=1;i<=n;i++) b[i]=a[i]; sort(b+1,b+n+1); m=1; for(int i=2;i<=n;i++) if(b[i]!=b[i-1]) b[++m]=b[i]; for(int i=1;i<=n;i++) a[i]=sol(a[i]); memset(sum,-1,sizeof sum); memset(ans,-1,sizeof ans); for(int i=1;i<=n;i++) pos[a[i]].push_back(i); memset(len,0,sizeof len); int c=0; LL s=0; for(int i=1;i<=m;i++){ for(UI j=0;j<pos[i].size();j++){ int p=pos[i][j]; bool f1=len[p-1],f2=len[p+1]; if(f1&&f2) c--; if(!f1&&!f2) c++; s++; if(f1) s+=len[p-1]<<1; if(f2) s+=len[p+1]<<1; if(f1&&f2) s+=len[p-1]*len[p+1]<<1; len[p]=1; if(f1) len[p]+=len[p-1]; if(f2) len[p]+=len[p+1]; if(f1) len[p-len[p-1]]=len[p]; if(f2) len[p+len[p+1]]=len[p]; } sum[b[i]]=s; if(ans[c]==-1||s*ans[c]>sum[ans[c]]*b[i]) ans[c]=b[i]; } } LL lastans; int tr[(N<<2)+3]; //tr[]=b[i] IL int ls(int i){return i<<1;} IL int rs(int i){return i<<1|1;} IL bool cmp(int x,int y){ if(x==-1) return false; if(y==-1) return true; return sum[x]*y>sum[y]*x; } IL void build(int i,int l,int r){ if(l==r){ tr[i]=ans[l]; return ; } int mid=(l+r)>>1; build(ls(i),l,mid); build(rs(i),mid+1,r); tr[i]=cmp(tr[ls(i)],tr[rs(i)])?tr[ls(i)]:tr[rs(i)]; } IL int qry(int i,int l,int r,int ql,int qr){ if(r<ql||qr<l) return -1; if(ql<=l&&r<=qr)return tr[i]; int mid=(l+r)>>1; if(qr<=mid) return qry(ls(i),l,mid,ql,qr); if(ql>mid) return qry(rs(i),mid+1,r,ql,qr); int x=qry(ls(i),l,mid,ql,qr); int y=qry(rs(i),mid+1,r,ql,qr); return cmp(x,y)?x:y; } int main(){ n=read(); t=read(); for(int i=1;i<=n;i++) a[i]=read(); a[n+1]=1e6+1; pre(); build(1,1,n); lastans=0; while(t--){ LL aa=read()%n,bb=read()%n,xx=read()%n,yy=read()%n; int l=(aa*lastans+xx-1+(n<<1))%n+1; int r=(bb*lastans+yy-1+(n<<1))%n+1; if(l>r) swap(l,r); int ansx=qry(1,1,n,l,r); LL anssum=ansx==-1?-1:sum[ansx]; printf("%lld %d\n%d %d %lld\n",anssum,ansx,l,r,lastans%n); lastans=anssum%n*ansx%n; } return 0; }
原文：https://www.cnblogs.com/Hansue/p/12920210.html
