分块9 区间众数（分块写法）

比眉伴天荒 2022-12-24 00:36 140阅读 0赞

求区间众数 更简单点的方法就是离线莫队，或者主席树，但是分块还是写写比较好

这题没测过，原因是我账号密码忘记了，反正就是好几个因素都有，导致我懒得测

[分块9题目链接][9]

思路就是 预处理出来每块到每块间的众数

对于一个L，R 要么是中间大的连续整块的众数为答案，要么就是不完整块中的某个数，一个数的个数可以提前存每个数出现的位置，二分求L,R间该数出现多少次

证明下时间复杂度

预处理每块到每块间的众数，总共有sqrt块 枚举l，跑到底是n复杂度，所以预处理是nsqrtn

枚举不完整块中某个数，枚举sqrt个数 每次都是log 询问m次

时间是mlongn sqrtn

（这也能卡过去？？？分块NB啊）

上代码(bug 很有点多） 所以还是换个题吧

[牛客网上一例题][Link 1]

差不多一个写法甚至代码还要短点（但是别人667ms过 我卡过去的就有点离谱）

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e5+7;
    #define int ll
    int n,m;
    int block,num;
    ll a[N];
    ll b[N];
    unordered_map<int,int>mp;
    int belong[N];
    int l[350],r[350];
    int sss[350][350];
    vector<int>son[N];
    int cnt[N];
    void init()
    {
        for(int i=1;i<=num;i++)
        {
    
            for(int j=i;j<=num;j++)
            {
                if(i!=j)
                sss[i][j]=sss[i][j-1];
                for(int k=l[j];k<=r[j];k++)
                {
                    cnt[b[k]]++;
                    sss[i][j]=max(sss[i][j],a[k]*cnt[b[k]]);
                   // cout<<k<<' '<<i<<' '<<j<<' '<<sss[i][j]<<endl;
                }
            }
            for(int j=l[i];j<=n;j++)
            cnt[b[j]]--;
    
        }
    }
    void build()
    {
        block=sqrt(n);
        num=n/block;
        if(n%block) num++;
        for(int i=1;i<=n;i++)
            belong[i]=((i-1)/block)+1;
        for(int i=1;i<=num;i++)
        {
            l[i]=(i-1)*block+1;
            r[i]=i*block;
        }
        r[num]=n;
        init();
    }
    ll cha(int L,int R)
    {
        ll ans=0;
    
       // cout<<'!'<<belong[L]<<' '<<belong[R]<<endl;
        if(belong[L]==belong[R])
        {
            for(int i=L;i<=R;i++)
            {
                int k=b[i];
                int d=upper_bound(son[k].begin(),son[k].end(),R)-lower_bound(son[k].begin(),son[k].end(),L);
                //cout<<k<<' '<<a[i]<<' '<<d<<endl;
                if(a[i]*d>ans)
                   ans=a[i]*d;
            }
        }
        else
        {
            ans=sss[belong[L]+1][belong[R]-1];
            //cout<<L+1<<' '<<R-1<<' '<<sss[L+1][R-1]<<"???"<<endl;
             for(int i=L;i<=r[belong[L]];i++)
            {
                int k=b[i];
                  int d=upper_bound(son[k].begin(),son[k].end(),R)-lower_bound(son[k].begin(),son[k].end(),L);
                  //cout<<k<<' '<<a[i]<<' '<<d<<endl;
                if(a[i]*d>ans)
                   ans=a[i]*d;
            }
            for(int i=l[belong[R]];i<=R;i++)
            {
                int k=b[i];
                  int d=upper_bound(son[k].begin(),son[k].end(),R)-lower_bound(son[k].begin(),son[k].end(),L);
                  //cout<<k<<' '<<a[i]<<' '<<d<<endl;
                if(a[i]*d>ans)
                   ans=a[i]*d;
            }
        }
       return ans;
    
    
    }
    signed main()
    {
       scanf("%d%d",&n,&m);
        int d=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%lld",&x);
            if(!mp[x]) mp[x]=++d;
            a[i]=x;
            b[i]=mp[x];
            son[b[i]].push_back(i);
        }
        build();
        /*for(int i=1;i<=d;i++)
        {
            for(int j=0;j<son[i].size();j++)
                cout<<son[i][j]<<' ';cout<<endl;
        }*/
        ll ans=0;
        for(int i=1;i<=m;i++)
        {
            int ll,rr;
            scanf("%lld%lld",&ll,&rr);
            ll=ll^ans;
            ll=ll%n+1;
            rr=rr^ans;
            rr=rr%n+1;
            if(ll>rr) swap(ll,rr);
            //cout<<ll<<' '<<rr<<" ????? ";
            ans=cha(ll,rr);
            printf("%lld\n",ans);
        }
    }
    /*
    1
    7
    1 3 4 2 7 6 5
    */

[9]: https://loj.ac/p/6285
[Link 1]: https://ac.nowcoder.com/acm/contest/8925/E