发布时间：2025-05-22

分块

在线求区间众数个数

$O(n \sqrt n)$预处理$f_{i,j}$表示$i$到$j$块的众数大小

询问：

如果$[L,R]$在同一个块直接询问

否则计算完整块的答案,$ans=f_{i+1,j-1}$

然后暴力遍历左右散块的数值，看看ans是否能增加，由于最多增加$2 \sqrt n$个元素，因此答案最多增加$2 \sqrt n$

总复杂度为$O((q+n)\sqrt n)$

void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1),nums;
    int mx=0;
    for(int i=1;i<=n;i++)cin>>a[i],nums.push_back(a[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
        mx=max(mx,a[i]);
    }
    vector<int> pos[mx+1],id(n+1);
    for(int i=1;i<=n;i++)id[i]=pos[a[i]].size(),pos[a[i]].push_back(i);
    vector<int> be(n+1),L,R;
    int block=sqrt(n)+1,tot=(n+block-1)/block;
    L.resize(tot+1),R.resize(tot+1);
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1,R[i]=min(n,i*block);
        for(int j=L[i];j<=R[i];j++)be[j]=i;
    }
    vector f(tot+1,vector<int>(tot+1));
    vector<int> t(mx+1);
    for(int i=1;i<=tot;i++){
        t.assign(mx+1,0);
        for(int j=i;j<=tot;j++){
            f[i][j]=f[i][j-1];
            for(int k=L[j];k<=R[j];k++){
                f[i][j]=max(f[i][j],++t[a[k]]);
            }
        }
    }
    t.assign(mx+1,0);
    int ans=0;
    while(m--){
        int l,r;
        cin>>l>>r;
        l^=ans,r^=ans;
        ans=0;
        if(be[l]==be[r]){
            for(int i=l;i<=r;i++)ans=max(ans,++t[a[i]]);
            for(int i=l;i<=r;i++)t[a[i]]=0;
            cout<<ans<<"\n";
            continue;
        }
        ans=f[be[l]+1][be[r]-1];
        for(int i=l;i<=R[be[l]];i++){
            int j=id[i];
            auto &v=pos[a[i]];
            while(j+ans<v.size()&&v[j+ans]<=r)ans++;
        }
        for(int i=r;i>=L[be[r]];i--){
            int j=id[i];
            auto &v=pos[a[i]];
            while(j-ans>=0&&v[j-ans]>=l)ans++;
        }
        cout<<ans<<"\n";
    }
}