蒲公英

Description

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为n的序列(a1,a2,...,ai,...,an) ，其中 ai 为一个正整数，表示第i棵蒲公英的种类编号。

而每次询问一个区间[l,r]，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的。

Input Format

第一行两个整数n,m，表示有n株蒲公英，m次询问。

接下来一行n 个空格分隔的整数ai ，表示蒲公英的种类。

再接下来m 行每行两个整数l0 , r0。我们令上次询问的结果为x（如果这是第一次询问，则x = 0）。

令l=(l0+x−1)mod n+1,r=(r0+x−1)mod n+1如果l>r，则交换l,r。

最终的查询区间为[l,r][l,r]。

Output Format

输出m 行。每行一个整数，表示每次询问的结果。

Sample Input

6 3
1 2 3 2 1 2
1 5
3 6
1 5

Sample Output

1
2
1

解析

这是一道经典的分块问题，由于众数不具有区间可加性，所以传统的线段树等数据结构全部都没用了。那么我们考虑使用分块算法，将序列(a)分为(T)块，每一块的长度为(frac{n}{T})，则对于每一个询问([l,r])，我们设(l)所在块的右边界为(L)，(r)所在块的左边界为(R)，那么就将原序列分为三部分([l,L],[L+1,R-1],[R,r])，显然([L+1,R-1])数若干个连续的块，那么区间([l,r])在众数就一定来自于以下两种情况：

(1.) 区间([L+1,R-1])的众数

(2.) 区间([l,L],[R,r])中的某个数

那么我们考虑如下的算法：

我们预处理出以每一个段边界为端点的区间众数，并对每一个数值建立一个(vector)，按顺序保存这个数值每一次出现的位置。

对于一个询问([l,r])，我们先直接选取([L+1,R-1])的答案做为备选答案，然后依次扫描([l,L],[R,r])中的每一个元素，利用二分查找在(vector)中找到这个数值在区间([l,r])第一次和最后一次出现的位置，两个(vector)的下标相减即为这个数在区间([l,r])中出现的次数，然后尝试更新答案。

此时，这个算法的时间复杂度为(O(nT+nm/T*log_2n))，取(T=sqrt{nlog_2n})，则时间复杂度最小为(O(nsqrt{nlog_2n}))。

(Code:)

#include <bits/stdc++.h>
using namespace std;
const int N=100020,SIZE=3020;
int n,t,raw[N],val[N],a[N];
int T,size,l[SIZE],r[SIZE],belo[N];
int cnt[N],mode[SIZE][SIZE];
vector < int > pos[N];
inline void input(void)
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]) , raw[++t] = a[i] ;
}
inline void setblocks(void)
{
    T = sqrt( n * log2(n) ) , size = n/T;
    for (int i=1;i<=T;i++)
    {
        if ( i*size > n ) break;
        l[i] = (i-1) * size + 1;
        r[i] = i * size;
    }
    if ( r[T] < n ) T++ , l[T] = r[T-1] + 1 , r[T] = n;
    for (int i=1;i<=T;i++)
        for (int j=l[i];j<=r[i];j++)
            belo[j] = i;
}
inline void discrete(void)
{
    sort( raw+1 , raw+t+1 );
    t = unique( raw+1 , raw+t+1 ) - (raw+1);
    for (int i=1;i<=n;i++)
        val[i] = lower_bound( raw+1 , raw+t+1 , a[i] ) - raw;
}
inline void init(void)
{
    for (int i=1;i<=n;i++)
        pos[ val[i] ].push_back(i);
    for (int i=1;i<=T;i++)
    {
        int Max = 0 , ans = 0;
        memset( cnt , 0 , sizeof cnt );
        for (int j=(i-1)*size+1;j<=n;j++)
        {
            cnt[ val[j] ]++;
            if ( Max < cnt[val[j]] || ( Max==cnt[val[j]] && raw[val[j]] < raw[ans] ) )
                Max = cnt[ val[j] ] , ans = val[j];
            mode[i][belo[j]] = ans;
        }
    }
}
inline int query(int ql,int qr)
{
    int L = belo[ql] , R = belo[qr];
    if ( L + 1 > R - 1 )
    {
        int Max = 0 , ans = 0;
        for (int i=ql;i<=qr;i++)
        {
            int tot = upper_bound( pos[val[i]].begin() , pos[val[i]].end() , qr ) 
                    - lower_bound( pos[val[i]].begin() , pos[val[i]].end() , ql );
            if ( tot > Max || ( tot==Max && raw[val[i]] < raw[ans] ) )
                Max = tot , ans = val[i];
        }
        return raw[ans];
    }
    int ans = mode[L+1][R-1];
    int Max = upper_bound(pos[ans].begin(),pos[ans].end(),r[R-1]) - lower_bound(pos[ans].begin(),pos[ans].end(),l[L+1]);
    for (int i=ql;i<=r[L];i++)
    {
        int tot = upper_bound( pos[val[i]].begin() , pos[val[i]].end() , qr ) 
                - lower_bound( pos[val[i]].begin() , pos[val[i]].end() , ql );
        if ( tot > Max || ( tot==Max && raw[val[i]] < raw[ans] ) )
            Max = tot , ans = val[i];
    }
    for (int i=l[R];i<=qr;i++)
    {
        int tot = upper_bound( pos[val[i]].begin() , pos[val[i]].end() , qr ) 
                - lower_bound( pos[val[i]].begin() , pos[val[i]].end() , ql );
        if ( tot > Max || ( tot==Max && raw[val[i]] < raw[ans] ) )
            Max = tot , ans = val[i];
    }
    return raw[ans];
}
inline void solve(void)
{
    int ql,qr;
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&ql,&qr);
        printf("%d
",query(ql,qr));
    }
}
int main(void)
{
    input();
    discrete();
    setblocks();
    init();
    solve();
    return 0;
}

<后记>