P4168 [Violet] 蒲公英

離散化+分塊 在線查詢區間眾數

由於a_i範圍是1e9的,記錄a_i出現的次數不方便直接用數組記錄，但是一共有n個數，我們就可以把它們排序去重，把a_i映射為在n個數中排第幾，這樣映射後的值域就小於n了，我們就能直接用數組記錄了，這就是離散化
將長度為 n 的數組分塊，每塊長度為 B=sqrt(n)
比如[0,B),[B,2*b)...[k*B,n)
對於所查詢的區間 [l ,r] 設l位於塊bl, r位於塊br,
|-------------------p1----------------p2---------------------|
| ------l-------------|-------------------|-----------r----------|

其中p1 = (bl+1)*B,p2 = br*B-1

該區間的眾數只可能為在 $[l,p1) ∪ (p2,r]$內出現的數 和 塊 $[bl+1,br-1]$的眾數之間

因為在加[l,p1) ∪ (p2,r]內出現的數的時候才會改變 塊 [bl+1,br-1]的眾數

當bl和br位於同一個塊或相鄰塊為了方便些代碼就直接暴力複雜度最大$2*sqrt(n)$

否則就是在cnt數組中只維護[l,p1) ∪ (p2,r]內出現的數 和 塊 [bl+1,br-1]的眾數,這些數字最多也是sqrt(n)級別的，在遍歷l->p_1和p_2->r用vis數組判斷是否已經加了某個數在[p1,p2]中的出現次數

p1->p2所有數出現的次數用前綴和維護
這樣總複雜度就是O(nlog(n)+(n+q)*sqrt(n))
ac代碼如下:

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

#define ull signed long long 
// #define int long long 



#define CINT \
// cin>>T;
void solve(){
    int n,q;cin>>n>>q;
    vector<int> a(n);
    for(int i = 0;i<n;i++){
        cin>>a[i];
    }
    vector<int> b = a;
    // 離散化
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    for(int i = 0;i<n;i++){
        a[i] = lower_bound(b.begin(),b.end(),a[i])-b.begin();
    }
    
    int B = sqrt(n);
    // 前綴和,存前i塊各個數字出現的次數
    vector<vector<int>> pre((n-1)/B+1,vector<int> (b.size()));
    for(int i = 0;i<n;i+=B){
        if(i!=0) pre[i/B] = pre[i/B-1];
        for(int j = i;j<min(n,i+B);j++){
            pre[i/B][a[j]]++;
        }
    }
    // f[i][j]表示第i塊到第j塊的眾數
    vector<vector<int>> f((n-1)/B+1,vector<int> ((n-1)/B+1));
    vector<int> cnt(b.size()),vis(b.size());
    for(int i = 0;i<=(n-1)/B;i++){
        int p = 0,mx = 0;
        fill(cnt.begin(),cnt.end(),0);
        for(int j = i;j<=(n-1)/B;j++){
            for(int k = j*B;k<min(n,j*B+B);k++){
                cnt[a[k]]++;
                if(cnt[a[k]]>mx || (cnt[a[k]]==mx and a[k]<p)){
                    p = a[k];
                    mx = cnt[a[k]];
                }
            }
            f[i][j] = p;
        }
    }
    fill(cnt.begin(),cnt.end(),0);

    auto upd = [&](int num,int& p,int& mx,int bl,int br){
        if(!vis[num]){ //判斷指定在中間區間的出現次數是否已經被加過
            vis[num] = 1;
            cnt[num] += pre[br-1][num]-pre[bl][num];
        }
        if(cnt[num]>mx || (cnt[num]==mx and num<p)){
            p = num;
            mx = cnt[num];
        }
    };

    int x = 0;
    while(q--){
        int l,r;cin>>l>>r;
        l = (l+x-1)%n+1;r = (r+x-1)%n+1;
        l--,r--;
        if(l>r) swap(l,r);
        int bl = l/B,br = r/B;
        int p = 0,mx = 0;
        if(br-bl<=1){ //區間長度小於2*sqrt(n)直接暴力
            for(int i = l;i<=r;i++){
                cnt[a[i]]++;
                if(cnt[a[i]]>mx || (cnt[a[i]]==mx and a[i]<p)){
                    p = a[i];
                    mx = cnt[a[i]];
                }
            }
            for(int i = l;i<=r;i++){
                cnt[a[i]] = 0;
            }
        }else{ 
            for(int i = l;i<(bl+1)*B;i++){
                cnt[a[i]]++;
                upd(a[i],p,mx,bl,br);
            }
            for(int i = br*B;i<=r;i++){
                cnt[a[i]]++;
                upd(a[i],p,mx,bl,br);
            }
            upd(f[bl+1][br-1],p,mx,bl,br);

            // 還原操作
            for(int i = l;i<(bl+1)*B;i++) cnt[a[i]] = vis[a[i]] = 0;
            for(int i = br*B;i<=r;i++) cnt[a[i]] = vis[a[i]] = 0;
            cnt[f[bl+1][br-1]] = vis[f[bl+1][br-1]] = 0;
        }
        x = b[p];
        cout<<b[p]<<"\n";
    }
}
signed main(){
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    CINT;
    while(T--) solve();
    return 0;
}