『蒲公英区间众数分块』

不念不忘少年蓝@ 2022-01-09 22:23 256阅读 0赞

--------------------

# 蒲公英 #

### 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(n\\sqrt\{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\n",query(ql,qr));
        }
    }
    int main(void)
    {
        input();
        discrete();
        setblocks();
        init();
        solve();
        return 0;
    }

--------------------

转载于:https://www.cnblogs.com/Parsnip/p/10901967.html