洛谷題目鏈接：[Violet] 蒲公英

一道分塊好題，調了整整一上午

一句話題意：在線求區間眾數

考慮到眾數沒有可加性，所以一般數據結構是不好維護的，這個時候就要用分塊了，分塊可以維護一些數據結構無法維護的復雜神秘數據，對于區間眾數就可以用分塊維護

考慮暴力做法，對于每一個詢問，暴力掃描，時間復雜度\(O(n^2)\)，顯然無法AC此題，故考慮分塊

將區間分為T塊，對于每個詢問，有以下情況

1. 查詢區間大小小于塊長
2. 查詢區間大小大于塊長

對于第一種情況，我們直接暴力掃描區間\(（l ，r）\)，時間復雜度\(O(T)\);
對于第二種情況，常見的分塊思想是將區間內整塊預處理，然后暴力掃描左右的散塊，所以，我們要預處理對于每個區間，從整塊i，到整塊j的眾數\(p（i，j)\)，預處理直接暴力枚舉，時間復雜度\(O（nT^2)\)。思考第二種情況的答案可能情況，發現只能來自整塊的眾數或者散塊中的數，感覺是廢話，注意這里散塊中的數不一定是散塊的眾數，所以每一個數都需要遍歷（筆者就是這里錯了，調了半天），這里，我們因為要遍歷每一個數出現次數，如果暴力跑與樸素算法無異，所以需要前綴和優化，對于\(s[i][j]\),表示從第1塊到第i塊，j出現的次數，可以\(O(1)\)求出整塊某個數出現次數。

對于最終答案，我們得出：

1. 通過p數組得出只在整塊出現的眾數。
2. 暴力統計散塊中數出現的次數，加上整塊中這個數出現次數，得出眾數。
3. 比較兩個答案，得出最終結果

最后，我們思考時間復雜度如何最優。時間瓶頸來自于\(O(nT^2)\)預處理，根據基本不等式，當\(T=\sqrt[3]{n}\)時時間復雜度最優，為\(O(n^{\frac{5}{3}})\)，實際測試下來，\(T=\sqrt{n}\)也可以過，本題解給出代碼為\(T=\sqrt{n}\)，這和暴力有什么區別。

等等，還有什么沒有考慮？再看一眼數據范圍，\(a\le1e9\),要離散化。

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10,M=500;
int s[M][N];
int p[M][M];
int a[N];
int b[N],num;
int c[N];
int d[N];
int n,m;
int T,cnt;
int cntnum[N];
struct node
{
    int l,r;
} pos[M];

void dis()
{
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        if(i==1 || a[i]!=a[i-1]) 
        b[++num]=a[i];
    }
}

int query(int x)
{
    return lower_bound(b+1,b+num+1,x)-b;
}

void init()
{
    for(int i=1;i<=n;i++) c[i]=query(d[i]);//c[i]表示下標為i的原數的離散值
    T=pow(n,1/2.0);
    int l=1,r=T;
    while(r<=n)
    {
        pos[++cnt].l=l;
        pos[cnt].r=r;
         l=r+1;
        r=l+T-1;
    }
    if(l<=n)
    {
        pos[++cnt].l=l;
        pos[cnt].r=n;
    }//分塊

    for(int i=1;i<=cnt;i++)
    {
        int l=pos[i].l,r=pos[i].r;
        for(int j=1;j<=num;j++)
        {
            int res=0;
            for(int i=l;i<=r;i++)
            {
                if(j==c[i]) res++;
            }
            s[i][j]=s[i-1][j]+res;
        }
    }// 預處理s數組,為前綴和數組

    int mx=0;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=i;j<=cnt;j++)
        {
            int l=pos[i].l,r=pos[j].r;
            memset(cntnum,0,sizeof(cntnum)),mx=0;
            for(int k=l;k<=r;k++)
            {
                int x=c[k];
                cntnum[x]++;
                if(cntnum[x]>mx || (cntnum[x]==mx && x<p[i][j])) mx=cntnum[x],p[i][j]=x;
            }
        }
    }//預處理p數組,注意，p存的是離散化后的值
}

pair<int,int> check(int pl,int pr,int l0,int r0)
{
    int r=pos[pl].l;
    int mx=0,res=0;//mx為眾數個數，res為眾數
    memset(cntnum,0,sizeof(cntnum));
    for(int i=l0;i<r;i++)
    {
        int x=c[i];
        int y=s[pr][x]-s[pl-1][x];
        cntnum[x]++;
        if(cntnum[x]+y>mx || (cntnum[x]+y==mx && x<res)) mx=cntnum[x]+y,res=x;
    }//左側散塊處理

    int l=pos[pr].r;
    for(int i=l+1;i<=r0;i++)
    {
        int x=c[i];
        int y=s[pr][x]-s[pl-1][x];
        cntnum[x]++;
        if(cntnum[x]+y>mx || (cntnum[x]+y==mx && x<res)) mx=cntnum[x]+y,res=x;
    }//右側散塊處理

    return {res,mx};
}

void solve()
{
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int l0,r0;
        scanf("%d%d",&l0,&r0);
        l0=(l0+ans-1)%n+1;
        r0=(r0+ans-1)%n+1;
        if(r0<l0) swap(r0,l0);
        ans=0;
        if(r0-l0+1<T)
        {
            int mx=0;
            memset(cntnum,0,sizeof(cntnum));
            for(int i=l0;i<=r0;i++)
            {
                int x=c[i];
                cntnum[x]++;
                if(cntnum[x]>mx || (cntnum[x]==mx && x<ans)) mx=cntnum[x],ans=x;
            }
            ans=b[ans];
        }
        else
        {
            int pl=ceil(l0/(double)T),pr=ceil(r0/(double)T);
            if(l0!=pos[pl].l) pl++;//最左側整塊
            if(r0!=pos[pr].r) pr--;//最右側整塊
            int now=p[pl][pr];
            pair <int,int> mode;
            mode=check(pl,pr,l0,r0);
            int sca=mode.second;//散塊眾數數量
            int cop=s[pr][now]-s[pl-1][now];//整塊的眾數數量
            if(cop>sca) ans=b[now];
            else
            {
                if(sca>cop) ans=b[mode.first];
                else ans=min(b[now],b[mode.first]);
            }
        }
        printf("%d\n",ans);
    }
}
int main(){
    // freopen("P4168_1.in","r",stdin);
    // freopen("ans.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),d[i]=a[i];
    dis();
    init();
    solve();
}

碼風冗長，請諒解