题解 P4168 【[Violet]蒲公英】

· · 题解

分块看似暴力，但其实确实是很优美。
在这种不满足区间可加性的题目中，分块就发挥了它的作用。

这道题的题意十分清晰，就是求区间众数。
想不出正解？我们可以用暴力。
对于每次询问开一个桶 t，从左至右扫一遍，找出众数。

直接开 10^9 的数组来统计肯定是会爆空间的,但是我们可以注意到，最多只可能有 40000 种不同的数值，所以只要离散化一下就可以暴力统计了。数组 a 存储原本的数值的排名，有序数组 b 存储原本的数值。
由于数据比较良心，加上快读不开 O_{2} 可以得到 45 分。

其实我们离正解并不远：
我们可以感性理解一下，如果我们把一个数列分成几段，那么如图所示，这个区间的众数一定会是橙色区域中的众数或者蓝色区域出现了的数。

设橙色部分中任意出现过的数字为 x，众数为 f。
若 x 原本的数量加上了在蓝色部分的数量仍然没有 f 原本的数量加上 f 在蓝色部分的数量之和大，那么它是不可能成为众数的。
没出现？视为原本在橙色部分的数量为 0 即可。
若在蓝色部分没出现且本来就不是众数，就更不可能打过众数了。
所以我们只需要考虑蓝色部分出现过的数字并将它和橙色部分的众数作比较即可。
因为蓝色部分长度和小于两格的长度，所以每次询问最多只需要查两格这么多，一下就省去了很多时间。
理解了这一部分，你就已经会这道题的正解了，剩下的是有一些细节的代码实现。

为了方便，我们需要预处理一个众数数组 f 和前缀和数组 s，f[i][j] 表示从第 i 个块到第 j 个块中的众数，s[i][j] 表示在前 i 块中 b[j] 出现的次数。

一些细节在代码中有注释： 

#include <cstdio>
#include <cmath>
#include <algorithm>
const int maxn=40000+10;
int a[maxn],b[maxn],s[200+10][maxn],f[200+10][200+10],t[maxn];
int block;//每块长度 

int read()
{
    int x=0,p=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if (ch=='-')
            p=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*p;
}
int get_block(int u)
{
    return (u-1)/block+1;
}
inline int min(int x,int y)
{
    return x<y?x:y;
}
int main()
{
    int n=read(),m=read();
    block=int(sqrt(n));//每一块的长度

    for (int i=1;i<=n;i++)
        b[i]=a[i]=read();
    std::sort(b+1, b+1+n);
    int sum=std::unique(b+1, b+1+n)-b-1,cnt=(n-1)/block+1;//sum是不同的数值个数，cnt是总块数 
    for (int i=1;i<=n;i++)
        a[i]=std::lower_bound(b+1, b+1+sum, a[i])-b;//这一部分是离散化，a存储的是a_i在b中的位置 

    for (int i=1;i<=cnt;i++)//预处理出f和s 
    {
        for (int j=block*(i-1)+1;j<=min(block*i, n);j++)//小心处理边界问题 
            s[i][a[j]]++;
        for (int j=1;j<=sum;j++)
            s[i][j]+=s[i-1][j];
    }
    for (int i=1;i<=cnt;i++)
        for (int j=i;j<=cnt;j++)
        {
            int MAX=f[i][j-1];
            for (int k=block*(j-1)+1;k<=min(block*j, n);k++)//不需要从头开始扫
                if ((s[j][a[k]]-s[i-1][a[k]]>s[j][MAX]-s[i-1][MAX])||(s[j][a[k]]-s[i-1][a[k]]==s[j][MAX]-s[i-1][MAX]&&a[k]<MAX))
                    MAX=a[k];
            f[i][j]=MAX;
        }

    int x=0;
    while(m--)
    {
        int l=(read()+x-1)%n+1,r=(read()+x-1)%n+1;
        if (l>r)
            std::swap(l, r);
        int bl=get_block(l),br=get_block(r),MAX=0;//bl是l所属块编号，br是r所属块的编号，MAX是众数在b中的下标 
        if (br-bl<=1)//如果区间长度小于等于两格，直接暴力 
        {
            for (int i=l;i<=r;i++)
                t[a[i]]++;
            for (int i=l;i<=r;i++)
                if (t[a[i]]>t[MAX]||(t[a[i]]==t[MAX]&&a[i]<MAX))
                    MAX=a[i];
            for (int i=l;i<=r;i++)//将桶清空 
                t[a[i]]=0;
        }
        else
        {
            for (int i=l;i<=block*bl;i++)
                t[a[i]]++;
            for (int i=block*(br-1)+1;i<=r;i++)
                t[a[i]]++;

            MAX=f[bl+1][br-1];
            for (int i=l;i<=block*bl;i++)//考虑蓝色部分出现的数是否会成为众数 
            {
                int pre=t[MAX]+s[br-1][MAX]-s[bl][MAX],now=t[a[i]]+s[br-1][a[i]]-s[bl][a[i]];
                if (now>pre||(now==pre&&MAX>a[i]))
                    MAX=a[i];
            }
            for (int i=block*(br-1)+1;i<=r;i++)
            {
                int pre=t[MAX]+s[br-1][MAX]-s[bl][MAX],now=t[a[i]]+s[br-1][a[i]]-s[bl][a[i]];
                if (now>pre||(now==pre&&MAX>a[i]))
                    MAX=a[i];
            }
            for (int i=l;i<=block*bl;i++)//将桶清空 
                t[a[i]]=0;
            for (int i=block*(br-1)+1;i<=r;i++)
                t[a[i]]=0;
        }
        x=b[MAX];
        printf("%d\n",x);
    }
    return 0;
}