分块入门9:P4168 区间众数查询O(n*sqrt(n))

题目链接：https://www.luogu.org/problemnew/show/P4168
题目大意：

思路一：

在线区间众数的分块做法比较多，这里提供一个思路：

首先离散化一下比较方便。

可以推导出：[L, R]的众数一定是整数块的众数，或者两个边块的数。

所以对于每次查询，众数的可能值最多有2sqrt(n)+1个

所以我们可以预处理f(i,j)表示第 i 块到第 j 块的众数（枚举 i 开个桶扫一遍）。

那么只要能快速得出一个数在某个区间内出现次数即可，每次只要比较至多2√n+1个元素的出现次数，这题就解决了。

由于没有修改，只要离散化以后，给每个数 x 开个vector，按顺序存下 x 出现的位置，每次询问 x 时把区间的左右端点放进对应 vector 二分一下即可。

根据均值不等式，可以算出分块大小大概是√(n/logn)

复杂度比较高，必须开O2才能过。

思路二：如果我们能够把整块区间求某个数的个数，复杂度降低到O(1)就完美了。

怎么降低呢？，用前缀和，s[i][j]表示：从1-第i块结束，数字j出现的次数。

现在对于一个众数可能值，我们只要求出现它在整块的个数，和两个边块的次数就行了。

我们统计次数时，必须把值映射一下：因为用桶去统计，每次mem一下。桶的大小太大就是O(n)了，只要2sqrt+1个就行了。

思路1：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//由块号寻找第一个块元素的下标
#define LL(x) ((x-1)*Len+1)
LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int a[50005], b[50005], cut[50005], vis[50005];
int f[505][505];
map<int, int> mp;

vector<int> v[50005];
int n, m, Len;

void pre(int x)
{
    memset(cut, 0, sizeof(cut));
    int mx=0, ans=0;
    for(int i=LL(x); i<=n; i++)
    {
        cut[a[i]]++;
        int t=b[i];
        if(cut[a[i]]>mx||cut[a[i]]==mx&&a[i]<ans)
        {
            ans=a[i], mx=cut[a[i]];
        }
        f[x][t]=ans;
    }
}

int query(int L, int R, int x)
{
    int t=upper_bound(v[x].begin(),v[x].end(),R)-lower_bound(v[x].begin(),v[x].end(),L);
    return t;
}

int query(int L, int R)
{
    int ans, mx;
    ans=f[b[L]+1][b[R]-1];
    mx=query(L, R, ans);
    for(int i=L;i<=min(LL(b[L]+1)-1, R); i++)
    {
        int t=query(L, R, a[i]);
        if(t>mx||t==mx&&a[i]<ans)
        {
            ans=a[i]; mx=t;
        }
    }
    if(b[L]!=b[R])
    {
        for(int i=LL(b[R]); i<=R; i++)
        {
            int t=query(L, R, a[i]);
            if(t>mx||t==mx&&a[i]<ans)
            {
                ans=a[i]; mx=t;
            }
        }
    }

    return ans;
}

void build(int n)
{
    Len=n/sqrt(n);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=(i-1)/Len+1;
    }
    for(int i=1;i<=n;i++)
    {
        mp[a[i]]=1;
    }
    int pos=1;
    for(map<int, int>::iterator it=mp.begin(); it!=mp.end(); it++)
    {
        it->second=pos++;
        vis[pos-1]=it->first;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=mp[a[i]];
        v[a[i]].push_back(i);
    }
    for(int i=1;i<=b[n];i++)
    {
        pre(i);
    }
}

int main()
{
    n=read(), m=read();
    build(n);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int L=read(), R=read();
        L=(L+ans-1)%n+1, R=(R+ans-1)%n+1;
        if(L>R)
        {
            swap(L, R);
        }
        ans=vis[query(L, R)];
        printf("%d\n", ans);
    }

    return 0;
}

思路二：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//由块号寻找第一个块元素的下标
#define LL(x) ((x-1)*Len+1)
LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int a[40050], b[40050], cut[40050], vis[40050];
int f[205][205];
int s[205][40050];
map<int, int> mp;
int n, m, Len;

void pre(int x)//初始化
{
    memset(cut, 0, sizeof(cut));
    int mx=0, ans=0;
    for(int i=LL(x); i<=n; i++)
    {
        cut[a[i]]++;
        int t=b[i];
        if(cut[a[i]]>mx||cut[a[i]]==mx&&a[i]<ans)
        {
            ans=a[i], mx=cut[a[i]];
        }
        f[x][t]=ans;
    }

    for(int i=1;i<LL(x+1);i++)
    {
        s[x][a[i]]++;
    }

}

int query(int L, int R, int x)//区间查询x出现的个数
{
    return s[b[R]][x]-s[b[L]-1][x];
}

int id[40050];
int BH(int L1, int R1, int L2, int R2)//边块处理
{
    int tot=1;
    for(int i=L1;i<=R1;i++)//初始化映射表
    {
        id[a[i]]=0;
    }
    for(int i=L2;i<=R2;i++)
    {
        id[a[i]]=0;
    }

    for(int i=L1;i<=R1;i++)//创建映射
    {
        if(id[a[i]]==0)
        {
            id[a[i]]=tot++;
        }
    }
    for(int i=L2;i<=R2;i++)
    {
        if(id[a[i]]==0)
        {
            id[a[i]]=tot++;
        }
    }
}

int query(int L, int R)
{
    int Size[505]={0};

    int ans=-1, mx=0;
    if(b[L]==b[R])
    {
        BH(L, R, 0, -1);
        for(int i=L;i<=R;i++)
        {
            Size[id[a[i]]]++;
            if(Size[id[a[i]]]>mx||Size[id[a[i]]]==mx&&ans>a[i])
            {
                ans=a[i]; mx=Size[id[a[i]]];
            }
        }
    }
    else
    {
        BH(L, LL(b[L]+1)-1, LL(b[R]), R);

        id[0]=f[b[L]+1][b[R]-1];//把区间众数加入桶
        Size[0]=s[b[R]-1][id[0]]-s[b[L]][id[0]];
        ans=id[0], mx=Size[0];

        for(int i=L;i<LL(b[L]+1);i++)
        {
            Size[id[a[i]]]++;
            int sum=s[b[R]-1][a[i]]-s[b[L]][a[i]];

            if(Size[id[a[i]]]+sum>mx||Size[id[a[i]]]+sum==mx&&ans>a[i])
            {
                ans=a[i]; mx=Size[id[a[i]]]+sum;
            }
        }
        for(int i=LL(b[R]);i<=R;i++)
        {
            Size[id[a[i]]]++;
            int sum=s[b[R]-1][a[i]]-s[b[L]][a[i]];
            if(Size[id[a[i]]]+sum>mx||Size[id[a[i]]]+sum==mx&&ans>a[i])
            {
                ans=a[i]; mx=Size[id[a[i]]]+sum;
            }
        }

    }

    return ans;
}

void build(int n)
{
    Len=n/sqrt(n);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=(i-1)/Len+1;
    }
    for(int i=1;i<=n;i++)
    {
        mp[a[i]]=1;
    }
    int pos=1;
    for(map<int, int>::iterator it=mp.begin(); it!=mp.end(); it++)
    {
        it->second=pos++;
        vis[pos-1]=it->first;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=mp[a[i]];
    }
    for(int i=1;i<=b[n];i++)
    {
        pre(i);
    }
}

int main()
{
    n=read(), m=read();
    build(n);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int L=read(), R=read();
        L=(L+ans-1)%n+1, R=(R+ans-1)%n+1;
        if(L>R)
        {
            swap(L, R);
        }
        ans=vis[query(L, R)];
        printf("%d\n", ans);
    }

    return 0;
}

/* 10 5 2 1 2 1 1 2 3 3 3 1 */