问题描述

大意就是:给你一个长度为n(n<=10000)的序列,再給你m(m<=20000)个询问,问你在给定区间[l,r]中的众数。(题目强制要求在线)

输入

第一行n, m
第二行给你序列(序列元素小于10^9)
接下来m行每行两个数l, r。

输出

m行,每行输出第m个询问的答案。

思路

由于众数是不方便进行区间合并的,因此不能够使用线段树或树状数组等数据结构。在这种情况下,分块是一种可能的选择。

分块时,我们考虑一个区间的众数只可能是:包含在区间中所有完整块的众数或者是包含在不完整的块中的数。这样,对于任意一个区间我们把范围缩小到了$2*size$($size$为块的大小)个数。

我们可以预处理出第i个完整块到第j个完整块中的众数,储存为f[i][j]。然后我们就考虑如何计算这些数在区间中的出现次数。我们可以用vector储存下标,然后用二分查找找出区间内的元素个数,这个即是该数在区间内的出现次数。

分析一下复杂度,设一个完整块的大小为size。处理询问的复杂度是$m*size*log(n)$,预处理的复杂度是$n*n/size$,这样size在大约200差不多就不会TLE了。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#define MAXN 40005
using namespace std;

int n, m, size, num, id, a[MAXN], pos[MAXN], L[MAXN], R[MAXN], ans;
int cnt[MAXN], val[MAXN], f[500][500];

map<int, int> mmp;
vector<int> vec[MAXN];

void init()
{
    size=sqrt(n), num=n/size;
    for(int i=1; i<=num; i++) L[i]=(i-1)*size+1, R[i]=i*size;
    if(R[num]<n) {L[++num]=R[num-1]+1; R[num]=n;}
    for(int i=1; i<=num; i++) for(int j=L[i]; j<=R[i]; j++) pos[j]=i;

    for(int i=1; i<=num; i++)
    {
        int maxn=0, ans=0;
        memset(cnt, 0, sizeof(cnt));
        for(int j=L[i]; j<=n; j++)
        {
            cnt[a[j]]++;
            int p=pos[j];
            if(cnt[a[j]]>maxn || (cnt[a[j]]==maxn && val[a[j]]<val[ans])) ans=a[j], maxn=cnt[a[j]];
            f[i][p]=ans;
        }
    }
}

int cal(int l, int r, int x)
{
    return upper_bound(vec[x].begin(), vec[x].end(), r)-lower_bound(vec[x].begin(), vec[x].end(), l);
}

int query(int l, int r)
{
    int ans=0, maxn=0, x=pos[l], y=pos[r];
    if(x==y)
    {
        for(int i=l; i<=r; i++)
        {
            int t=cal(l, r, a[i]);
            if(t>maxn || (t==maxn && val[a[i]]<val[ans])) ans=a[i], maxn=t;
        }
    }
    else
    {
        ans=f[x+1][y-1];
        maxn=cal(l, r, ans);
        for(int i=l; i<=R[x]; i++)
        {
            int t=cal(l, r, a[i]);
            if(t>maxn || (t==maxn && val[a[i]]<val[ans])) ans=a[i], maxn=t;
        }
        for(int i=L[y]; i<=r; i++)
        {
            int t=cal(l, r, a[i]);
            if(t>maxn || (t==maxn && val[a[i]]<val[ans])) ans=a[i], maxn=t;
        }
    }
    return ans;
}

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a2.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
        if(!mmp[a[i]])
        {
            mmp[a[i]]= ++id;
            val[id]=a[i];
        }
        a[i]=mmp[a[i]];
        vec[a[i]].push_back(i);
    }
    init();
    for(int i=1; i<=m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l=(l+ans-1)%n+1;
        r=(r+ans-1)%n+1;
        if(l>r) swap(l, r);
        ans=val[query(l, r)];
        printf("%d\n", ans);
    }
}

1 对 “BZOJ2724 蒲公英 [分块]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注