洛谷 P4168 [Violet]蒲公英 题解【分块】【枚举】

点击量：242

有一点点练码力吧……但是分块思维还是很重要的。

目录

题目背景

亲爱的哥哥：

你在那个城市里面过得好吗？

我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……

最近村子里长出了一大片一大片的蒲公英。一刮风，这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面，让哥哥看看就好了呢！

哥哥你要快点回来哦！

爱你的妹妹 Violet

Azure 读完这封信之后微笑了一下。

“蒲公英吗……”

题目描述

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为$ n$的序列$ {a_1,a_2\dots a_n}$，其中$ a_i$为一个正整数，表示第$ i$棵蒲公英的种类编号。

而每次询问一个区间$ [l,r]$，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的。

输入输出格式

输入格式：

第一行两个整数$ n,m$，表示有$ n$株蒲公英，$ m$次询问。

接下来一行$ n$个空格分隔的整数$ a_i$ ，表示蒲公英的种类。

再接下来$ m$行每行两个整数$ l_0,r_0$，我们令上次询问的结果为$ x$（如果这是第一次询问， 则$ x=0$）。

令$ l=(l_0+x-1)\bmod n + 1,r=(r_0+x-1) \bmod n + 1$，如果$ l>r$，则交换$ l,r$。

最终的询问区间为$ [l,r]$。

输出格式：

输出$ m$行。每行一个整数，表示每次询问的结果。

输入输出样例

输入样例#1：

6 3 
1 2 3 2 1 2 
1 5 
3 6 
1 5

输出样例#1：

1 
2 
1

说明

对于$ 20\%$的数据，保证$ 1\le n,m \le 3000$。

对于$ 100\%$的数据，保证$ 1\le n \le 40000,1\le m \le 50000,1\le a_i \le 10^9$。

题解：

分块好题啊。

首先要离散化，输出答案时也要转回来。

分块就是大段维护局部朴素。这里是大段预处理，因为段长是$ \sqrt{n}$，所以预处理出任意两段的信息都是$ O((\sqrt{n})^2)=O(n)$的。具体到各种信息，乘上的复杂度也各不相同。

比如我要存块区间$ [l,r]$的最小众数，可能用$ O(n)$的时间操作一下前缀和就可以了。

不过话说回来，$ O(n)$处理是不能接受的。如果一个一个枚举计数，可以做到均摊$ O(\sqrt{n})$。

也即每次以某一个块$ i$为起点，然后枚举元素，遇到整块$ j$时用当前的众数更新$ f[i][j]$。因为实时更新众数是$ O(1)$的，所以整个过程下来是$ O(n)$。共$ O(\sqrt{n})$块，这里的处理总复杂度就是$ O(n^{\frac{3}{2}})$了。

然后对于每次询问，把大块的众数$ x$求出来，然后比较两边多出来的元素。这些元素总共只有$ O(\sqrt{n})$个，其余的元素个数不会超过$ x$出现的次数。因此只需要临时计算大块中这些元素的个数，加上多出来的一些，与答案$ x$比较就可以了。

块边界方面的细节还是比较多的。

Code：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
using std::max;
using std::min;
using std::map;
map<int,int> e;
int a[40010],to[40010];
int sum[205][40010],Sum[40010];
int f[205][205];
int stk[40010],tp=0;
int main()
{
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        e[a[i]]=1;
    }
    int cnt=0,base=sqrt(n);
    for(map<int,int>::iterator it=e.begin();it!=e.end();++it)
    {
        to[++cnt]=it->first;
        it->second=cnt;
    }
    for(int i=1;i<=n;++i)
    {
        a[i]=e[a[i]];
        ++Sum[a[i]];
        if(i%base==0)
            for(int j=1;j<=cnt;++j)
                sum[i/base][j]=Sum[j];
    }
    int tot=n/base;
    for(int i=1;i<=tot;++i)
    {
        memset(Sum,0,sizeof(Sum));
        int tmp=0;
        for(int j=(i-1)*base+1;j<=n;++j)
        {
            ++Sum[a[j]];
            if(Sum[a[j]]>Sum[tmp]||(Sum[a[j]]==Sum[tmp]&&a[j]<tmp))
                tmp=a[j];
            if(j%base==0)
                f[i][j/base]=tmp;
        }
    }
    int l,r;
    memset(Sum,0,sizeof(Sum));
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&l,&r);
        l=(l+ans-1)%n+1;
        r=(r+ans-1)%n+1;
        if(l>r)
        {
            int tmp=l;
            l=r;
            r=tmp;
        }
        int L=ceil((double)l/base)+1;
        int R=r/base;
        ans=0;
        if(L<=R)
        {
            int k=f[L][R];
            stk[++tp]=k;
            Sum[k]=sum[R][k]-sum[L-1][k];
            ans=k;
        }
        int up=min(base*(L-1),r);
        for(int j=l;j<=up;++j)
        {
            int k=a[j];
            if(!Sum[k])
            {
                stk[++tp]=k;
                if(L<=R)
                    Sum[k]=sum[R][k]-sum[L-1][k];
            }
            ++Sum[k];
            if(Sum[k]>Sum[ans]||(Sum[k]==Sum[ans]&&k<ans))
                ans=k;
        }
        for(int j=max(up,base*R)+1;j<=r;++j)
        {
            int k=a[j];
            if(!Sum[k])
            {
                stk[++tp]=k;
                if(L<=R)
                    Sum[k]=sum[R][k]-sum[L-1][k];
            }
            ++Sum[k];
            if(Sum[k]>Sum[ans]||(Sum[k]==Sum[ans]&&k<ans))
                ans=k;
        }
        ans=to[ans];
        printf("%d\n",ans);
        while(tp)
            Sum[stk[tp--]]=0;
    }
    return 0;
}