P4168 蒲公英 • CoderXL's Blog

题目废话好多

给定数列，每次查询区间 $[l,r]$ 上的众数。强制在线。

众数这个统计量不具有什么好的性质——它对区间不满足结合律，因此无法使用线段树、树状数组等等实用的数据结构。

考虑根号分块。

性质#

这里有一个十分关键的性质：

如果 $x$ 是数列 $\{a_i\}$ 在区间 $[l,r]$ 上的众数，那么对于任意 $k\in [l,r]$ ， $x$ 要么是区间 $[l,k]$ 上的众数，要么在区间 $[k+1,r]$ 上出现过。

更一般地说，如果 $x$ 既不是某个子区间的众数，也没有出现在该子区间的补中，那么 $x$ 不可能是父区间的众数。

证明比较显然。

思路#

有了这个性质，结合上分块的优化，做法就呼之欲出了。

预处理#

将数列 $\{a_i\}$ 根号分块。然后求解第 $i$ 块到第 $j$ 块（左闭右闭）之间的众数，记为 $md[i][j]$ .

根据之前的性质， $md[i][j]$ 要么等于 $md[i][j-1]$ ，要么等于某个在第 $j$ 块中出现过的数。因此 $O(\sqrt n)$ 地遍历第 $j$ 块中的每个数 $a_k$ ，记录 $v=a_k$ 在第 $i$ 块到第 $j$ 块中出现的次数 $cnt[v]$ ，然后检查最大的 $cnt[v]$ 是否大于 $cnt[md[i][j-1]]$ . 若大于，则 $\displaystyle{md[i][j]=\arg\max_{v} cnt[v]}$ ，即第 $i$ 块到第 $j$ 块的众数为 $v$ ；否则就 $md[i][j]=md[i][j-1]$ .

然后外层枚举 $i,j$ ，总时间复杂度 $O(\sqrt n \sqrt n \sqrt n)=O(n\sqrt n)$ .

细心的读者发现，上述思路中标黄的部分需要我们维护某个数 $v$ 在第 $i$ 块到第 $j$ 块中出现的次数。这可以通过提前预处理好一个前缀和数组 $s[i][v]$ ，表示前 $i$ 块（包含）中 $v$ 的出现次数，然后每次 $s[j][v]-s[i-1][v]$ 来查询得到。当然也可以通过在最外层枚举 $i$ 的时候清空 $cnt$ ，然后在内层循环中不断累计来实现。这道题由于要配合后续的查询，因此采用前者。

查询#

由于我们已经预处理好了所有 $md[i][j]$ ，也即所有连续若干块内的众数。而一个查询区间 $[l,r]$ 可以被分成三个部分：中间连续的若干块 + 左侧的一小部分 + 右侧的一小部分。根据性质，众数要么是「中间连续的若干块」的众数，要么是在左右两小部分中出现过的数。仿照预处理即可。

额外细节#

当一个区间有两种以上众数时，题目额外要求了取数值最小的众数。只需要在转移的时候补充判断相等的情况。

千万别忘了在线输入的时候，要更新 $x$ ！！！

代码#

//
//  main.cpp
//  P4168
//
//  Created by Leo Xia on 2026/4/20.
//

#include <bits/stdc++.h>
using namespace std;

const int N = 40010, sN = 210;
int n,m,nn,len;
int a[N],g[N],s[sN][N],md[sN][sN],id[N],cnt[N];

void build()
{
    for(int i=1;i<=id[n];i++)
    {
        for(int j=i;j<=id[n];j++)
        {
            int mxi=md[i][j-1],mx=cnt[mxi];
            for(int k=(j-1)*len+1;id[k]==j;k++)
            {
                cnt[a[k]]++;
                if(cnt[a[k]]>mx||(cnt[a[k]]==mx&&a[k]<mxi))
                {
                    mx=cnt[a[k]];mxi=a[k];
                }
            }
            md[i][j]=mxi;
        }
        memset(cnt,0,sizeof(cnt));
    }
}

int query(int l,int r)
{
    int lid=id[l],rid=id[r];
    int mx=0,mxi=0;
    if(rid<=lid+1)
    {
        for(int i=l;i<=r;i++)
        {
            cnt[a[i]]++;
            if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&a[i]<mxi))
            {
                mx=cnt[a[i]];mxi=a[i];
            }
        }
        for(int i=l;i<=r;i++)cnt[a[i]]=0;
        return mxi;
    }
    mxi=md[lid+1][rid-1];mx=s[rid-1][mxi]-s[lid][mxi];
    for(int i=l;id[i]==lid;i++)
    {
        int&ccnt=++cnt[a[i]],&ai=a[i];
        if(ccnt+s[rid-1][ai]-s[lid][ai]>mx||(ccnt+s[rid-1][ai]-s[lid][ai]==mx&&ai<mxi))
        {
            mx=ccnt+s[rid-1][ai]-s[lid][ai];mxi=ai;
        }
    }
    for(int i=r;id[i]==rid;i--)
    {
        int&ccnt=++cnt[a[i]],&ai=a[i];
        if(ccnt+s[rid-1][ai]-s[lid][ai]>mx||(ccnt+s[rid-1][ai]-s[lid][ai]==mx&&ai<mxi))
        {
            mx=ccnt+s[rid-1][ai]-s[lid][ai];mxi=ai;
        }
    }
    for(int i=l;id[i]==lid;i++)cnt[a[i]]=0;
    for(int i=r;id[i]==rid;i--)cnt[a[i]]=0;
    return mxi;
}

signed main()
{
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        g[i]=a[i];
        id[i]=(i-1)/len+1;
    }
    sort(g+1,g+n+1);
    nn=unique(g+1,g+n+1)-g-1;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(g+1,g+nn+1,a[i])-g;
        s[id[i]][a[i]]++;
    }
    for(int i=1;i<=id[n];i++)for(int j=1;j<=nn;j++)
        s[i][j]+=s[i-1][j];
    build();
    int op=0;
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        l=(l+op-1)%n+1;
        r=(r+op-1)%n+1;
        if(l>r)swap(l,r);
        op=g[query(l,r)];// Forgotten! FUCK
        cout<<op<<'\n';
    }
    return 0;
}

cpp

后记#

为什么要使用分块#

在区间上统计一些指标并要求支持修改的时候，有一些数据结构可供选择，但都或多或少需要被统计的指标满足一些良好性质。而分块，就是对性质要求最弱的数据结构。

下面是一张对比表：

数据结构	要求的性质	空间复杂度	单次查询/修改时间复杂度	初始化时间复杂度	经典应用
树状数组	交换律、结合律、存在逆元	$O(n)$	$O(\log n)$	$O(n\log n)$ 特殊情况 $O(n)$	区间和
ST 表	结合律、幂等律	$O(n\log n)$	$O(1)$ / 不支持修改	$O(n\log n)$	区间最大值、区间 GCD
线段树	结合律	$O(n)$ 常数大	$O(\log n)$ 常数大	$O(n)$	以上所有、最大子段和、区间方差
分块	无要求	$O(n)$	$O(\sqrt n)$ / 看情况可能从 $O(1)$ 到 $O(n)$	$O(n)$	以上所有、区间众数

查询区间众数 ↗是分块的经典应用之一。