嗯,今天也是我第一次学分块,所以更下题解和分块.辛格大佬说这个题就是莫队的板子
分块一般是将一个区间分成sqrt(n)块,然后对于进行处理,比如说今天我们这个题目求区间众数.
我们处理出两个数组,一个f[i][j]表示第i块到第j块的众数是多少,另外一个s[i][j]表示前i块中j出现次数.处理完这两个数组,我们就很容易知道假如给定一个区间l-r要我们求这个区间的众数,怎么求呢?假设l-r不跨一个区间.那么直接暴力求就好了,假如跨的区间＞1,那么众数产生会是哪些地方呢?我们画个图.
图片说明
emm,有点丑...不过并不影响什么,显然众数只可能是f[2][4]和l-2/4-r里面的一个数,如此这个题就做完了..下面代码有注释的..
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=4e4+5;
const int M=2e2+10;
int a[N],b[N];//a数组用来存值,b数组用来离散化
int f[M][M],s[M][N];//f数组是用来存第i块到第j块的众数,s数组是用来存前i块中值为j的数量有多少.
int to[N],block,cnt;//开个桶数组.块的大小.块的数量
inline int ask(int x)//查询x在哪一块.
{
    return (x-1)/block+1;
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);//m组查询.
    for(int i=1;i<=n;i++)   
    {
        scanf("%d",&a[i]);//输入
        b[i]=a[i];
    }
    block=(int)sqrt(n);//块的大小
    cnt=(n-1)/block+1;//块的数量
    sort(a+1,a+1+n);
    int sum=unique(a+1,a+1+n)-a-1;
    for(int i=1;i<=n;i++)//离散化
    {
        b[i]=lower_bound(a+1,a+1+sum,b[i])-a;
    }
    for(int i=1;i<=cnt;i++)//处理s数组
    {
        for(int j=(i-1)*block+1;j<=min(n,i*block);j++)
        {
            s[i][b[j]]++;
        }
        for(int j=1;j<=sum;j++)
        {
            s[i][j]+=s[i-1][j];
        }
    }
    int mx;//众数
    for(int i=1;i<=cnt;i++)//处理f数组
    {
        for(int j=i;j<=cnt;j++)
        {
            mx=f[i][j-1];//没选肯定众数是上一个区间的众数.
            for(int k=(j-1)*block+1;k<=min(n,j*block);k++)
            {
                if(s[j][b[k]]-s[i-1][b[k]]>s[j][mx]-s[i-1][mx]||(s[j][b[k]]-s[i-1][b[k]]==s[j][mx]-s[i-1][mx]&&b[k]<mx))
                {
                    mx=b[k];
                }
            }
            f[i][j]=mx;
        }
    }
    int ans=0,_l,_r;
    while(m--)
    {
        scanf("%d%d",&_l,&_r);
        int l=(_l+a[ans]-1)%n+1;
        int r=(_r+a[ans]-1)%n+1;
        if(l>r) swap(l,r);
        if(ask(r)-ask(l)<=1)
        {
            for(int i=l;i<=r;i++)
            {
                to[b[i]]++;
            }
            for(int i=l;i<=r;i++)
            {
                if(to[b[i]]>to[ans]||(to[b[i]]==to[ans]&&b[i]<ans))
                {
                    ans=b[i];
                }
            }
            for(int i=l;i<=r;i++)   to[b[i]]=0;
        }
        else
        {
            int bl=ask(l);
            int br=ask(r);
            ans=f[bl+1][br-1];//中间是众数.
            for(int i=l;i<=bl*block;i++) to[b[i]]++;
            for(int i=(br-1)*block+1;i<=r;i++) to[b[i]]++;
            for(int i=l;i<=bl*block;i++)
            {
                if((to[b[i]]+s[br-1][b[i]]-s[bl][b[i]]>to[ans]+s[br-1][ans]-s[bl][ans])||(to[b[i]]+s[br-1][b[i]]-s[bl][b[i]]==to[ans]+s[br-1][ans]-s[bl][ans]&&b[i]<ans))
                {
                    ans=b[i];
                }
            }
            for(int i=(br-1)*block+1;i<=r;i++)
            {
                if((to[b[i]]+s[br-1][b[i]]-s[bl][b[i]]>to[ans]+s[br-1][ans]-s[bl][ans])||(to[b[i]]+s[br-1][b[i]]-s[bl][b[i]]==to[ans]+s[br-1][ans]-s[bl][ans]&&b[i]<ans))
                { 
                    ans=b[i];
                }
            }
            //清空
            for(int i=l;i<=bl*block;i++)          to[b[i]]=0;
            for(int i=(br-1)*block+1;i<=r;i++)    to[b[i]]=0;
        }
        cout<<a[ans]<<endl;
    }
    return 0;
}

友情提示下两个易错点,注意是对离散化的答案取模,以及分块的中间块的处理..