P4168 [Violet] 蒲公英 (离散化+分块 在线查询区间众数)

福如东海小仙女

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;
    }
    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 = lower_bound(b.begin(),b.end(),a)-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[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[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]++;
                if(cnt[a]>mx || (cnt[a]==mx and a<p)){
                    p = a;
                    mx = cnt[a];
                }
            }
            for(int i = l;i<=r;i++){
                cnt[a] = 0;
            }
        }else{ 
            for(int i = l;i<(bl+1)*B;i++){
                cnt[a]++;
                upd(a,p,mx,bl,br);
            }
            for(int i = br*B;i<=r;i++){
                cnt[a]++;
                upd(a,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] = vis[a] = 0;
            for(int i = br*B;i<=r;i++) cnt[a] = vis[a] = 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;
}

来源：https://www.cnblogs.com/hyhgfrgh/p/19687542