题目大意
对于给定的数列 \(a\)，选择一个数 \(x\)，定义其得分为数列中所有小于等于 \(x\) 的数形成的若干个连续区间的平方和除以 \(x\) 所得到的数。
现进行多次询问，每次询问给定两个数 \(l,r\)，要求出一个得分最大的 \(x\)，满足数列中所有小于等于 \(x\) 的数形成的若干个连续区间的个数在 \(l\) 到 \(r\) 之间。
强制在线。
思路分析
容易发现，满足条件的得分最大的 \(x\) 一定是数列中的一个数。考虑反证法，如果满足条件的得分最大的 \(x\) 不是数列中的数，那么一定可以将 \(x\) 变成数列中最大的小于 \(x\) 的数，分子不变，分母变小，得分增大。
那么这就意味着 \(x\) 的取值只有 \(O(n)\) 级别，又因为得分没有单调性（容易构造，比如 1 100 4 3），所以考虑从小到大枚举 \(x\) 的取值。
由于 \(x\) 单调，那么数列中被标记的数的个数也一定单调，那么就可以用并查集维护所有小于等于 \(x\) 的数形成的连通块，\(O(n\log n)\) 预处理出对于 \(x\) 的每一个取值，得到的得分和连通块的块数。
具体的说，先将原数列排序，从小到大枚举 \(x\)（这里指的是枚举 \(x\) 的可能取值），对于每一个数列中等于 \(x\) 的数，判断是否与其左右的数合并即可。合并时可以 \(O(1)\) 更新信息。
对于每一个询问，我们发现，在预处理时，已经得到了每一个 \(x\) 所对应的区间个数。那么我们可以对于每一个区间长度的所有可能的 \(x\) 所对应的得分取一个最值，再对于区间长度的得分 RMQ 即可。
时间复杂度由 RMQ 的数据结构决定，但不低于 \(O(n\log n)\)。
- 一些细节
数据在解密时可能爆 long long，可以开 __int128 或读入后先取模。
在无解时输出 -1 -1 后将 lastans 设为 \(1\)。
初始时 lastans 为 \(0\)。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1001000,M=1010;
typedef long long ll;
int T,n,tot,S,m,in1,in2,in3,in4;
int fa[N],siz[N],a[N],c[N];
int maxn[N],maxi[M],l[M],r[M],pos[N];//空间一定要开够
ll now,ans[N],lastans;
vector <int> v[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
x=find(x);y=find(y);
if(x==y) return ;
now-=1ll*siz[x]*siz[x]+siz[y]*siz[y];//去除贡献
tot--;siz[x]+=siz[y];fa[y]=x;
now+=1ll*siz[x]*siz[x];//增加贡献
}
bool compare(int x,int y){return 1ll*ans[x]*c[y]<1ll*ans[y]*c[x];}//分数比较大小，c[x] 是实际的 x，ans[x] 是得分的分子
void query_t(int &res,int x,int y,int g[]){
for(int i=x;i<=y;i++)
if(compare(res,g[i])) res=g[i];
}
int query(int x,int y){//RMQ
int res=0;
if(pos[x]==pos[y]){query_t(res,x,y,maxn);return res;}
query_t(res,x,r[pos[x]],maxn);
query_t(res,l[pos[y]],y,maxn);
query_t(res,pos[x]+1,pos[y]-1,maxi);
return res;
}
int main(){
memset(l,0x3f,sizeof l);
scanf("%d%d",&n,&T);
S=sqrt(n);m=n;//RMQ 使用分块
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
c[i]=a[i];
pos[i]=(i-1)/S+1;//每个数所在块
}
for(int i=1;i<=n;i++){//初始化块端点和并查集
fa[i]=i;siz[i]=1;
l[pos[i]]=min(l[pos[i]],i);
r[pos[i]]=max(r[pos[i]],i);
}
sort(c+1,c+m+1);//离散化
m=unique(c+1,c+m+1)-c-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(c+1,c+m+1,a[i])-c;
v[a[i]].push_back(i);//对于每一个离散化后的值开一个 vector 存下标
}
ans[0]=-1;
c[0]=1;
for(int x=1;x<=m;x++){
now+=v[x].size();tot+=v[x].size();//等于 x 的数有 v[x].size() 个
//now 表示平方和，tot 表示个数
for(auto it:v[x]){//遍历所有等于 x 的数
if(it!=1&&a[it-1]<=x) merge(it,it-1);//特判边界
if(it!=n&&a[it+1]<=x) merge(it,it+1);//如果旁边的数 <= x 就一定被标记或即将被标记
}
ans[x]=now;
if(compare(maxn[tot],x)){
maxn[tot]=x;//更新单点答案
if(compare(maxi[pos[tot]],x))
maxi[pos[tot]]=x;//更新块内答案
}
}
while(T--){
scanf("%d%d%d%d",&in1,&in2,&in3,&in4);
in1%=n;in2%=n;in3%=n;in4%=n;//读入后取模
int l=(1ll*in1*lastans%n+in3-1+n)%n+1;
int r=(1ll*in2*lastans%n+in4-1+n)%n+1;
if(l>r) swap(l,r);
int res=query(l,r);
if(!res){printf("-1 -1\n%d %d %lld\n",l,r,lastans);lastans=1;}
else{
printf("%lld %d\n%d %d %lld\n",ans[res],c[res],l,r,lastans);
lastans=1ll*(ans[res]%n)*(c[res]%n)%n;
}
}
return 0;
}