洛谷 P4168 [Violet] 蒲公英

历尽千辛万苦终于AC了这道题目。。。

---

我们考虑1个区间\([l,r]\)，

被其完整包含的块的区间为\([L,R]\)

那么众数的来源？

1.\([l,L)\)或\((R,r]\)中出现的数字

2.\([L,R]\)中的众数

思路逐渐清晰起来

我们考虑维护这样的两个量

\(P[i][j]\)表示从第i块到第j块的区间（最小）众数

\(S[i][j]\)表示前i块中j的出现次数

先直接离散化或者hash或者unordered_map处理，然后维护

结合刚才的思路，不难得到：

1.求出\([l,L)\)或\((R,r]\)中出现的数字的出现次数

2.求出\([L,R]\)中的众数的出现次数

3.进行比较判断

4.完结撒花！！！

贴一个可见度并不高的代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=6e4+10;

int alpha=3;

unordered_map<int,int> p,q;//双向映射

int tot,n,m,len;

int b[maxn];

int num[maxn];

int mode[500][500];

int s[500][maxn];

int t[maxn],vis[maxn];//用于处理询问

void init()

{

    for(int i=1;i<=b[n];++i)

    {

        memset(vis,0,sizeof vis);

        int tmp=1999999999,nu=0;

        for(int j=i;j<=b[n];++j)

        {

            for(int k=(j-1)*len+1;k<=min(n,j*len);++k)

            {

                ++vis[num[k]];

                if(vis[num[k]]==nu&&p[num[k]]<tmp)

                        tmp=p[num[k]],nu=vis[num[k]];

                else if(vis[num[k]]>nu)

                    tmp=p[num[k]],nu=vis[num[k]];

            }

            mode[i][j]=q[tmp];

        }

    }//维护第i块到第j块的区间众数

    for(int i=1;i<=b[n];++i)

    {

        for(int j=1;j<=n;++j)

            s[i][num[j]]=s[i-1][num[j]];

        for(int j=(i-1)*len+1;j<=min(n,i*len);++j)

            ++s[i][num[j]];

    }

}

int solve(int l,int r)

{

    if(b[r]-b[l]<=alpha)

    {

        int tmp=1999999999,nu=0;

        for(int i=l;i<=r;++i)

            t[num[i]]=0;

        for(int i=l;i<=r;++i)

        {

            ++t[num[i]];

            if(t[num[i]]==nu&&p[num[i]]<tmp)

                tmp=p[num[i]],nu=t[num[i]];

            else if(t[num[i]]>nu)

                tmp=p[num[i]],nu=t[num[i]];

        }

        return tmp;

    }

    t[mode[b[l]+1][b[r]-1]]=0;

    vis[mode[b[l]+1][b[r]-1]]=0;

    for(int i=l;i<=min(n,b[l]*len);++i)

        t[num[i]]=0,vis[num[i]]=0;

    for(int i=r;i>=(b[r]-1)*len+1;--i)

        t[num[i]]=0,vis[num[i]]=0;

    for(int i=l;i<=min(n,b[l]*len);++i) ++t[num[i]];

    for(int i=r;i>=(b[r]-1)*len+1;--i)	++t[num[i]];

    int tmp=0,nu=0;

    for(int i=l;i<=min(n,(b[l])*len);++i)

    {

        if(!vis[num[i]])

        {

            vis[num[i]]=1;

            int qaq=s[b[r]-1][num[i]]-s[b[l]][num[i]]+t[num[i]];

            if(qaq==nu&&p[num[i]]<tmp)

                tmp=p[num[i]],nu=qaq;

            else if(qaq>nu)

                tmp=p[num[i]],nu=qaq;

        }

    }

    for(int i=r;i>=(b[r]-1)*len+1;--i)

    {

        if(!vis[num[i]])

        {

            vis[num[i]]=1;

            int qaq=s[b[r]-1][num[i]]-s[b[l]][num[i]]+t[num[i]];

            if(qaq==nu&&p[num[i]]<tmp)

                tmp=p[num[i]],nu=qaq;

            else if(qaq>nu)

                tmp=p[num[i]],nu=qaq;

       }

    }

    int qwq=mode[b[l]+1][b[r]-1];

    if(nu<s[b[r]-1][qwq]-s[b[l]][qwq]+t[qwq]) return p[qwq];

    else if(nu==s[b[r]-1][qwq]-s[b[l]][qwq]+t[qwq]) return min(p[qwq],tmp);

	return tmp;

}

int main()

{

//	freopen("test.txt","r",stdin);

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;++i)

    {

        int tmp;

        scanf("%d",&tmp);

        if(!q[tmp])

            ++tot,q[tmp]=tot,num[i]=tot,p[tot]=tmp;

        else num[i]=q[tmp];

    }

    len=sqrt(n);

    for(int i=1;i<=n;++i)

        b[i]=(i-1)/len+1;

    init();

    int l0,r0,lst=0;

    for(int i=1;i<=m;++i)

    {

        scanf("%d%d",&l0,&r0);

        int l=(l0+lst-1)%n+1,r=(r0+lst-1)%n+1;

        if(l>r) swap(l,r);

        lst=solve(l,r);

        printf("%d\n",lst);

    }

    return 0;

}

洛谷 P4168 [Violet] 蒲公英的相关教程结束。