RE 求助

Exber @ 2021-08-08 19:11:36

by Exber @ 2021-08-08 19:11:54

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>

#define MS 40005

using namespace std;

int n,m,a[MS];
vector<int> v,pos[MS];
int where[MS];
int blo,L[MS],R[MS],who[MS],ans[305][305],times[305][305];
int tot[MS];

inline void init()
{
    blo=sqrt(n);
    for(int i=1;i<=blo;i++)
    {
        L[i]=(i-1)*blo+1;
        R[i]=i*blo;
    }
    R[blo]=n;
    for(int i=1;i<=n;i++)
    {
        who[i]=(i-1)/blo+1;
    }
    for(int i=1;i<=blo;i++)
    {
        memset(tot,0,sizeof(tot));
        int maxx=0,nans=0;
        for(int j=i;j<=blo;j++)
        {
            for(int k=L[j];k<=R[j];k++)
            {
                tot[a[k]]++;
                if(maxx<tot[a[k]])
                {
                    maxx=tot[a[k]];
                    nans=a[k];
                }
                else if(maxx==tot[a[k]]&&v[a[k]-1]<v[nans-1])
                {
                    nans=a[k];
                }
            }
            times[i][j]=maxx;
            ans[i][j]=nans;
        }
    }
}

inline int que(int l,int r)
{
    if(who[l]==who[r])
    {
        memset(tot,0,sizeof(tot));
        int maxx=0,res=0; 
        for(int i=l;i<=r;i++)
        {
            tot[a[i]]++;
            if(maxx<tot[a[i]])
            {
                maxx=tot[a[i]];
                res=v[a[i]-1]; 
            }
            else if(maxx==tot[a[i]]&&v[a[i]-1]<res)
            {
                res=v[a[i]-1];
            }
        }
        return res;
    }
    int maxx=times[who[l]+1][who[r]-1],res=v[ans[who[l]+1][who[r]-1]-1];
    for(int i=l;i<=R[who[l]];i++)
    {
        while(where[i]+maxx<pos[a[i]].size()&&pos[a[i]][where[i]+maxx]<=r)
        {
            maxx++;
            res=v[a[i]-1];
        }
        if(where[i]+maxx-1<pos[a[i]].size()&&pos[a[i]][where[i]+maxx-1]<=r&&v[a[i]-1]<res)
        {
            res=v[a[i]-1];
        }
    }
    for(int i=L[who[r]];i<=r;i++)
    {
        while(where[i]-maxx>=0&&pos[a[i]][where[i]-maxx]>=l)
        {
            maxx++;
            res=v[a[i]-1];
        }
        if(where[i]-maxx+1>=0&&pos[a[i]][where[i]-maxx+1]>=l&&v[a[i]-1]<res)
        {
            res=v[a[i]-1];
        }
    }
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
        pos[a[i]].push_back(i);
        where[i]=pos[a[i]].size()-1;
    }
    init();
    int lstans=0;
    for(int i=1;i<=m;i++)
    {
        int l0,r0;
        scanf("%d%d",&l0,&r0);
        int l=(l0+lstans-1)%n+1,r=(r0+lstans-1)%n+1;
        if(r<l)
        {
            int t=r;
            r=l;
            l=t;
        }
        printf("%d\n",lstans=que(l,r)); 
    }
    return 0;
}

by Lemon_X @ 2021-08-08 19:16:02

%%%

by Eason_AC @ 2021-08-08 19:18:07

@lovely_ckj

蒟蒻用暴力意外过了此题

想知道怎么个暴力法

by 一只大龙猫 @ 2021-08-08 19:19:34

Cull ball

顺带%%%

by Terraria @ 2021-08-08 19:19:42

@Eason_AC 亲测离散化 + 暴力找众数（连 O2 都不用开） 就能过

by Exber @ 2021-08-08 19:20:22

@Eason_AC

将

inline int que(int,int)

中的

    if(who[l]==who[r])
    {
        memset(tot,0,sizeof(tot));
        int maxx=0,res=0; 
        for(int i=l;i<=r;i++)
        {
            tot[a[i]]++;
            if(maxx<tot[a[i]])
            {
                maxx=tot[a[i]];
                res=v[a[i]-1]; 
            }
            else if(maxx==tot[a[i]]&&v[a[i]-1]<res)
            {
                res=v[a[i]-1];
            }
        }
        return res;
    }

改为

    if(true)
    {
        memset(tot,0,sizeof(tot));
        int maxx=0,res=0; 
        for(int i=l;i<=r;i++)
        {
            tot[a[i]]++;
            if(maxx<tot[a[i]])
            {
                maxx=tot[a[i]];
                res=v[a[i]-1]; 
            }
            else if(maxx==tot[a[i]]&&v[a[i]-1]<res)
            {
                res=v[a[i]-1];
            }
        }
        return res;
    }

即可……

by jr_inf @ 2021-08-08 19:20:27

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

by 54fwk @ 2021-08-08 19:20:46

数组太小了吧。

by Eason_AC @ 2021-08-08 19:21:21

@lovely_ckj 牛啊，这都能过

by 54fwk @ 2021-08-08 19:21:23

我猜的