题解 P5012 【水の数列】

· · 题解

这题的题目背景使我们明白，原来神题都是多次加强造出来的（划掉

观察题目中给出的这个得分的性质，发现随着 x 的增大，并不存在任何单调性，是一个多峰函数。直接考虑暴力枚举 x，并处理出对于 x 的每个取值下，被标记的区间长度的平方和和区间个数。

对于限定区间个数 tot \in [l,r] 的询问，在预处理后，已知 x 的每个取值能够取到的区间个数，对于每一区间个数取一个最值，再维护区间个数在 \in [l,r] 的最值即可，使用线段树/\text{ST} 表等 \text{RMQ} 数据结构都可，但毒瘤出题人 \color{black}\text{C}\color{red}\text{Yjian} 卡空间，只能使用空间复杂度为 O(n + \sqrt n) 的分块（分块什么时候是数据结构了

对于一个确定的 x ，处理出被标记的区间长度的平方和和区间个数，这是一个连通性的问题，可以使用带权并查集维护。

小于等于 x 的标记也很好实现，从小到大标记。并且我们发现，如果将 a_i 从小到大排序，一个 \exists i\geq 1,a_{i-1}<x<a_i 的 x 对答案不产生影响，因为这个影响也同样产生在 x=a_{i-1}。那么离散化后按照上述思路处理即可。

Show the Code

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#define get_block(x) (x-1)/block+1 
#define min(a,b) ((a)<(b)? (a):(b))
typedef long long ll;
std::vector<int> t[1000001];
ll v[1000001];
int fa[1000001],size[1000001],a[1000001],c[1000001],mx[1000001],maxn[1001];
inline int read() {
    register int x=0,f=1;register char s=getchar();
    while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
inline void swap(int &x,int &y) {int tmp=y;y=x;x=tmp;}
inline int find(int x) {return x==fa[x]? x:fa[x]=find(fa[x]);}
inline void merge(int x,int y,ll &res1,int &res2) {
    int fx=find(x),fy=find(y);
    if(fx!=fy) {
        res1-=(ll)size[fx]*size[fx]+(ll)size[fy]*size[fy]; --res2;
        fa[fy]=fx;size[fx]+=size[fy];res1+=(ll)size[fx]*size[fx];
    }
}
inline bool cmp(int x,int y) {return v[x]*1ll*c[y]<v[y]*1ll*c[x];}
int main() {
    int n=read(),T=read(),num=0,block=sqrt(n);
    for(register int i=1;i<=n;++i) c[++num]=a[i]=read(),fa[i]=i;
    std::sort(c+1,c+1+num); num=std::unique(c+1,c+1+num)-c-1; 
    for(register int i=1;i<=n;++i) {a[i]=std::lower_bound(c+1,c+1+num,a[i])-c;t[a[i]].push_back(i);}
    ll now=0; int tot=0;
    v[0]=-1,c[0]=1;
    for(register int x=1;x<=num;++x) {
        for(register int i=0;i<t[x].size();++i) {size[t[x][i]]=1; ++now; ++tot;}
        for(register int i=0;i<t[x].size();++i) {
            if(t[x][i]!=1&&a[t[x][i]-1]<=x) merge(t[x][i],t[x][i]-1,now,tot);
            if(t[x][i]!=n&&a[t[x][i]+1]<=x) merge(t[x][i],t[x][i]+1,now,tot);
        }
        v[x]=now;
        if(cmp(mx[tot],x)) {
            mx[tot]=x;
            if(cmp(maxn[get_block(tot)],x)) maxn[get_block(tot)]=x;
        }
    }
    ll ans=0;
    while(T--) {
        int a=read()%n,b=read()%n,x=read()%n,y=read()%n;
        int l=((a*1ll*ans%n+x-1)%n+n)%n+1,r=((b*1ll*ans%n+y-1)%n+n)%n+1;
        if(l>r) swap(l,r);
        int bl=get_block(l),br=get_block(r),id=0;
        if(bl==br) {for(register int i=l;i<=r;++i) if(cmp(id,mx[i])) id=mx[i];}
        else {
            for(register int i=l;i<=min(bl*block,n);++i) if(cmp(id,mx[i])) id=mx[i];
            for(register int i=bl+1;i<br;++i) if(cmp(id,maxn[i])) id=maxn[i];
            for(register int i=(br-1)*block+1;i<=r;++i) if(cmp(id,mx[i])) id=mx[i];
        }       
        if(id==0) {printf("-1 -1\n%d %d %d\n",l,r,ans);ans=1%n;}
        else {printf("%lld %d\n%d %d %d\n",v[id],c[id],l,r,ans);ans=(v[id]%n)*1ll*(c[id]%n)%n;}
    }
    return 0;
}