题解 P5012 水の数列

· · 题解

题目不带修，故 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;
}