洛谷4168 BZOJ2724 蒲公英 分塊+離散化

題目連結

題意：

給你一個n個數，有m次詢問，每次詢問一個區間内最小的衆數是多少,強制線上。

題解:

這種東西想想也感覺線段樹之類的很難維護，是以就用相對更暴力、功能更強的分塊。

具體做法：

由于每個數的值域是 [0,109] [ 0 , 10 9 ] ，是以要先離散化一下。然後我們對下标分成 n−−√ n 塊，我們首先考慮維護衆數，我們知道，對于整塊的衆數，我們可以預處理出來，但是對于在塊外的部分，隻有在塊外出現的這些數才可能加上整塊裡的比原來隻考慮整塊的答案大，是以記錄哪些數字是在塊外出現了的，然後每個數在每一整塊内出現的次數可以用字首和預處理出來，是以每次隻需要處理 O(n−−√) O ( n ) 級别的那些在塊外的數就可以了。至于還要滿足最小，那麼就記錄離散化後的每一種數出現了多少次和目前出現次數最多的數離散化後的值，更新答案時不僅是在有一個數比目前衆數出現次數更多時更新，還要在有一個數與目前衆數出現次數一樣但是數值比目前衆數更小的情況更新。

最後總的複雜度就是 O(mn−−√) O ( m n ) 。

代碼：

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

int n,m,pos[],sz,lastans,t[],a[],cur,ji[];
int cnt[][],f[][],shu,bl[],br[],ci[];
inline int query(int l,int r)
{
    int tot=,ans=,val=;
    if(pos[l]==pos[r]||pos[l]+==pos[r])
    {
        for(int i=l;i<=r;++i)
        ci[a[i]]=;
        for(int i=l;i<=r;++i)
        {
            ++ci[a[i]];
            if(ci[a[i]]>ci[ans]||(ci[a[i]]==ci[ans]&&a[i]<ans))
            ans=a[i];
        }
    }
    else
    {
        ans=f[pos[l]+][pos[r]-];
        val=cnt[ans][pos[r]-]-cnt[ans][pos[l]];
        for(int i=l;i<=br[pos[l]];++i)
        ji[++tot]=a[i];
        for(int i=bl[pos[r]];i<=r;++i)
        ji[++tot]=a[i];
        for(int i=;i<=tot;++i)
        ci[ji[i]]=cnt[ji[i]][pos[r]-]-cnt[ji[i]][pos[l]];
        for(int i=;i<=tot;++i)
        ++ci[ji[i]];
        for(int i=;i<=tot;++i)
        {
            if(ci[ji[i]]>val||(ci[ji[i]]==val&&ji[i]<ans))
            {
                ans=ji[i];
                val=ci[ji[i]];
            }
        }
        for(int i=;i<=tot;++i)
        ci[ji[i]]=;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;++i)
    {
        scanf("%d",&a[i]);
        t[i]=a[i];
    }
    sort(t+,t+n+);
    shu=unique(t+,t+n+)-t-;
    for(int i=;i<=n;++i)
    a[i]=lower_bound(t+,t+shu+,a[i])-t;
    sz=sqrt(n);
    for(int i=;i<=n;++i)
    {
        pos[i]=(i-)/sz+;
        if(!bl[pos[i]])
        bl[pos[i]]=i;
        br[pos[i]]=i;
    }   
    for(int i=;i<=n;++i)
    ++cnt[a[i]][pos[i]];
    for(int i=;i<=pos[n];++i)
    {
        for(int j=;j<=shu;++j)
        cnt[j][i]+=cnt[j][i-];
    }
    for(int i=;i<=pos[n];++i)
    {
        memset(ji,,sizeof(ji));
        cur=;
        for(int j=i;j<=pos[n];++j)
        {
            for(int k=bl[j];k<=br[j];++k)
            {
                ++ji[a[k]];
                if(ji[a[k]]>ji[cur]||(ji[a[k]]==ji[cur]&&a[k]<cur))
                cur=a[k];
            }
            f[i][j]=cur;
        }
    }
    for(int i=;i<=m;++i)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        l=(l+lastans-)%n+;
        r=(r+lastans-)%n+;
        if(r<l)
        swap(l,r);
        lastans=t[query(l,r)];
        printf("%d\n",lastans);
    }
    return ;
}