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

作者: wjyyy 分类: 分块,枚举,解题报告 发布时间: 2019-02-02 22:21

点击量:70

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

题目背景

亲爱的哥哥:

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

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

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

哥哥你要快点回来哦!

爱你的妹妹 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;
}

说点什么

avatar
  Subscribe  
提醒
/* */