为什么我用暴力过了此题

Exber @ 2021-08-07 22:02:22

by Exber @ 2021-08-07 22:02:44

code：

#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=L[i];j<=R[i];j++)
        {
            tot[a[j]]++;
            if(maxx<tot[a[j]])
            {
                maxx=tot[a[j]];
                nans=a[j];
            }
            else if(maxx==tot[a[j]]&&v[a[j]-1]<v[nans-1])
            {
                nans=a[j];
            }
        }
        times[i][i]=maxx;
        ans[i][i]=nans;
        for(int j=i+1;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(true||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<pos[a[i]].size()&&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 Exber @ 2021-08-07 22:03:05

注意 if(true||who[l]==who[r])

by ByGones @ 2021-08-07 22:05:56

@lovely_ckj 这题暴力本来就能过，而且您的暴力码量远超分块

by Exber @ 2021-08-07 22:07:21

啊这

by cyffff @ 2021-08-07 22:07:35

zyx

by ByGones @ 2021-08-07 22:07:41

@lovely_ckj 能帮我调调分块吗（

by Exber @ 2021-08-07 22:07:42

我本来是调试分块的，结果 A 了

by Exber @ 2021-08-07 22:08:17

@卞宇轩 等我用分块 A 了这题先

by Sol1 @ 2021-08-07 22:11:00

你的暴力未免慢了点

by 听取MLE声一片 @ 2021-08-07 22:12:15

@lovely_ckj 其实这题很水的，我n^{5/3}的跑的飞快，跟暴力似的