洛谷 P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

Vanilla_chan · 2021-03-18 11:39:15 · 题解

题目描述

给你一个长为 n 的序列 a，m 次询问，每次查询一个区间的众数的出现次数，强制在线。

Solution

An easy problem

本文将以从洛谷 P4168 [Violet]蒲公英的转换视角来解决这道题。蒲公英这道题不仅数据范围友好，题目背景也不错。

以下默认块大小为\sqrt n .

前置知识：基本的分块，求众数。

先来讨论一下蒲公英那道题是怎么做的：

首先离散化。

预处理出从第 i 块到第 j 块中的众数 zs_{i,j} 。可以枚举 i ,枚举 j ，再枚举块内元素开一个桶统计。时间复杂度 O(n\sqrt{n}) ，空间复杂度 O(n)+O(\sqrt n\times \sqrt n)=O(n) 。

预处理出第 1 块到第 i 块这个区间[1,i] 中数字 x 出现的次数 cnt_{i,x} 。可以枚举i后，先将 (\forall x)cnt_{i-1,x} 拷贝到 cnt_{i,x} ，再统计当前块 i 。时间复杂度 O(\sqrt n\times (n+\sqrt n))=O(n\sqrt n) ，空间复杂度 O(n\sqrt n) 。

对于每一个询问 (l,r) ，讨论其是否在一个块内。若是同块，就使用桶暴力统计。若不在一个块内，则将其拆为两个散块和一个整块。

首先答案 ans=zs_{i,j} ，再向两边拓展，看看散块内的数 x 是否可能成为比 ans 出现次数更大的数。具体的，整块中 x 出现的次数可以用之前预处理出的 cnt_{j,x}-cnt_{i-1,x} 这种形式表示。散块中的 x 使用桶来统计即可。

询问的时间复杂度为 O(\sqrt n+2\times \sqrt n)=O(\sqrt n) 。

Code

//预编译部分已略去
#define N 40010
#define S 300
int n,m,s,block,L[N],R[N],belong[N],zs[S][S],cnt[N],a[N],f[S][N],sum[N];
int rys[N];
int lastans;
map<int,int>ys;
int main()
{
    n=read();m=read();
    s=sqrt(n);
    block=n/s;
    for(int i=1;i<=s;i++)
    {
        L[i]=n/s*(i-1)+1;
        R[i]=n/s*i;
    }
    R[s]=n;
    for(int i=1;i<=s;i++)
    {
        for(int j=L[i];j<=R[i];j++)
        {
            belong[j]=i;
        }
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ys[a[i]]=0;
    }
    int rank=1;
    for(map<int,int>::iterator it=ys.begin();it!=ys.end();it++)
    {
        rys[rank]=it->first;
        it->second=rank;
        rank++;
    }
    for(int i=1;i<=n;i++) a[i]=ys[a[i]];
//  for(int i=1;i<=n;i++) cout<<a[i]<<endl;
    for(int i=1;i<=s;i++)
    {
        memset(cnt,0,sizeof(cnt));
        for(int j=i;j<=s;j++)
        {
            zs[i][j]=zs[i][j-1];
            for(int k=L[j];k<=R[j];k++)
            {
                cnt[a[k]]++;
                if(cnt[a[k]]>cnt[zs[i][j]] || (cnt[a[k]]==cnt[zs[i][j]]&&a[k]<zs[i][j])) zs[i][j]=a[k];
            }
        }
    }
    for(int i=1;i<=s;i++)
    {
        for(int j=1;j<=ys.size();j++) f[i][j]=f[i-1][j];
        for(int j=L[i];j<=R[i];j++)
        {
            f[i][a[j]]++;
        }
    }
    for(int t=1,x,y;t<=m;t++)
    {
        cin>>x>>y;
        x=(x+lastans-1)%n+1;
        y=(y+lastans-1)%n+1;
        if(x>y) x^=y^=x^=y;
        LL ans=0;
        if(belong[y]-belong[x]<=3)
        {
            for(int i=x;i<=y;i++) sum[a[i]]=0;
            for(int i=x;i<=y;i++)
            {
                sum[a[i]]++;
                if(sum[a[i]]>sum[ans] || (sum[a[i]]==sum[ans]&&a[i]<ans)) ans=a[i];
            }
        }
        else
        {
            ans=zs[belong[x]+1][belong[y]-1];
            sum[ans]=0;
            for(int i=x;i<=R[belong[x]];i++)
            {
                sum[a[i]]=0;
            }
            for(int i=L[belong[y]];i<=y;i++)
            {
                sum[a[i]]=0;
            }
            for(int i=x;i<=R[belong[x]];i++)
            {
                sum[a[i]]++;
                if(f[belong[y]-1][a[i]]-f[belong[x]][a[i]]+sum[a[i]]>f[belong[y]-1][ans]-f[belong[x]][ans]+sum[ans] || (f[belong[y]-1][a[i]]-f[belong[x]][a[i]]+sum[a[i]]==f[belong[y]-1][ans]-f[belong[x]][ans]+sum[ans]&&a[i]<ans)) ans=a[i];
            }
            for(int i=L[belong[y]];i<=y;i++)
            {
                sum[a[i]]++;
                if(f[belong[y]-1][a[i]]-f[belong[x]][a[i]]+sum[a[i]]>f[belong[y]-1][ans]-f[belong[x]][ans]+sum[ans] || (f[belong[y]-1][a[i]]-f[belong[x]][a[i]]+sum[a[i]]==f[belong[y]-1][ans]-f[belong[x]][ans]+sum[ans]&&a[i]<ans)) ans=a[i];
            }
        }
        cout<<(lastans=rys[ans])<<endl;
    }
    return 0;
}

回到正题

蒲公英的数据范围十分友好： n\le 4\times 10^4,m\le 10^5 。所以我们完全能够开下 cnt_{s,n} 。

但是P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III的数据范围就不那么友好了： n,m\le 5\times 10^5 。

这两道题有许多的共同点：区间众数，无修改，要离散化，数据范围看上去是根号做法的。

但是也有一些不同点：无法预处理前缀块的桶（因为空间开不下），求的是众数出现的次数而非众数是谁（其实差不多，但是求出现次数的话需要处理的信息可以少了点）

无法开桶，那么可以用另一种方式表达这个桶吗？可以的。

首先离散化，预处理 zs_{i,j} 就不必多费阐述了吧。

使用 n 个 vector 中存放下标， vector_{x,i} 表示数x第i次出现的下标。由于是 vector ，所以总空间依然是 O(n) 的。

再记 p_i 表示 i 这位上的数 x 在其 vector_{x} 中在第几位。

显然预处理这个的时间复杂度是 O(n) 的。

对于每个询问，我们还是类似于上面的那样，同块暴力统计即可；

否则依然将其拆分。首先 ans=zs_{i,j} （注意，这里的 zs_{i,j} 不再是 [i,j] 块内的众数，而是其出现的次数），在考虑两边的散块中，数 x 的出现次数能否更新 ans 。

比如，现在正在考虑在左侧散块的下标为i的数x能否更新ans。 p_i 是i之前有多少个 x ，那么至少要存在第 ans+p_i 个x ，且 ans+p_i 要在[l,r]的数据范围以内，答案就可以被更新，ans++。

若在右侧则同理。

Code

//预编译部分已略去
#define N 500010
#define S 800
int n,m,s,block,L[N],R[N],belong[N],zs[S][S],cnt[N],a[N],sum[N],pos[N];
vector<int>vec[N];
int lastans;
map<int,int>ys;
int main()
{
//  freopen("5048.in","r",stdin);
//  freopen("5048-hsh.out","w",stdout);
    n=read();m=read();
    s=sqrt(n);
    block=n/s;
    for(int i=1;i<=s;i++)
    {
        L[i]=n/s*(i-1)+1;
        R[i]=n/s*i;
    }
    R[s]=n;
    for(int i=1;i<=s;i++)
    {
        for(int j=L[i];j<=R[i];j++)
        {
            belong[j]=i;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ys[a[i]=read()]=0;
    }
    int rank=1;
    for(map<int,int>::iterator it=ys.begin();it!=ys.end();it++)
    {
        it->second=rank;
        rank++;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=ys[a[i]];
        vec[a[i]].push_back(i);
        pos[i]=vec[a[i]].size()-1;
    }
//  for(int i=1;i<=n;i++) cout<<a[i]<<endl;
    for(int i=1;i<=s;i++)
    {
        memset(cnt,0,sizeof(cnt));
        for(int j=i;j<=s;j++)
        {
            zs[i][j]=zs[i][j-1];
            for(int k=L[j];k<=R[j];k++)
            {
                cnt[a[k]]++;
                zs[i][j]=max(zs[i][j],cnt[a[k]]);
            }
        }
    }
    int ans=0;
    for(int t=1,x,y;t<=m;t++)
    {
        x=read();
        y=read();
        x^=ans;
        y^=ans;
        if(x>y) swap(x,y);
        ans=0;
        if(belong[y]-belong[x]<=3)
        {
            for(int i=x;i<=y;i++) sum[a[i]]=0;
            for(int i=x;i<=y;i++)
            {
                sum[a[i]]++;
                ans=max(ans,sum[a[i]]);
            }
        }
        else
        {
            ans=zs[belong[x]+1][belong[y]-1];
            for(int i=x,now;i<=R[belong[x]];i++)
            {
                now=pos[i];
                while(now+ans<vec[a[i]].size()&&vec[a[i]][now+ans]<=y) ans++;         
            }
            for(int i=L[belong[y]],now;i<=y;i++)
            {
                now=pos[i];
                while(now-ans>=0&&vec[a[i]][now-ans]>=x) ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

小节

分块模板题的训练就到此完结了。

但是分块的玄学美妙优雅暴力之处不仅仅于此。

比如根号平衡等。

比如P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III这道题其实还可以二分查找最后一个 \le r 的数，使得总时间复杂度变为 O(NT+MN/T*\log t)\stackrel{T=\sqrt{N\log N}}{\longrightarrow}O(N\sqrt{N\log N}) [^1]级别的。

大概是因为这只是 Ynoi 的模拟赛吧，就没有那么卡时间。

但是遇到毒瘤题，根号平衡是一种很重要的卡常方法。

以后遇到了卡常分块的话可以记录一下。

[^1]: 算法竞赛进阶指南 0x44