USACO 2025 Open, Gold - B

_JoeyJ_ · 2025-04-06 15:27:05 · 题解

博客园食用更佳。

比较唐的根号做法。

记 tot_x 为 A 中 x 的出现次数，不难发现题目中的限制等价于选取 i,j 使得 \displaystyle tot_i+tot_j\geq \max_k tot_k。

考虑对 lim=\displaystyle \max_k tot_k 阈值分治：

• 对于 lim\leq B 的情况：

  记 \displaystyle mx_i=\max_{tot_j\geq i} j，\displaystyle mn_i=\min_{tot_j\geq i} j。考虑枚举最后可能的 tot_i，则答案为 \displaystyle \max_{i\geq 1} mx_i-mn_{lim-i}。

• 对于 lim \gt B 的情况：

  称 tot_x \geq \lceil \frac B2 \rceil 的 x 为大数，则由 \displaystyle \sum_i tot_i =n 可知大数的个数不会超过 \lfloor\frac{2n}B\rfloor 个，同时一组合法的 (i,j) 中至少有一个大数。考虑枚举大数，则答案为：\displaystyle \max_{tot_i \geq \lceil \frac B2 \rceil} \max\{i-mn_{lim-tot_i},mx_{lim-tot_i}-i\}。

现在的问题是如何 O(1) 查 mn_i 和 mx_i。

使用 set 做到 O(\log n) 查询是简单的。发现每次修改 \Delta tot_i \in \{-1,0,1\}，所以实际上受到影响的只有 O(1) 个位置，丢到数组上先修改后查询即可。

时间复杂度 O(n\log n+q(\log n+\sqrt n))。

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+9;
const int B=4e2;

int a[N],cnt[N],mx[N],mn[N],n,q;
set<int> s[N],all,big;
inline void Update(int x){
    mx[x]=mx[x+1],mn[x]=mn[x+1];
    if(s[x].size()){
        mx[x]=max(mx[x],*s[x].rbegin());
        mn[x]=min(mn[x],*s[x].begin());
    }
}
inline void Veto(int x){
    all.erase(cnt[x]);
    s[cnt[x]].erase(x);
    Update(cnt[x]);
    if(cnt[x]>=(B>>1)) big.erase(x);
    cnt[x]--;
    if(cnt[x]>=(B>>1)) big.insert(x);
    all.insert(cnt[x]);
    s[cnt[x]].insert(x);
}
inline void Vote(int x){
    all.erase(cnt[x]);
    s[cnt[x]].erase(x);
    if(cnt[x]>=(B>>1)) big.erase(x);
    cnt[x]++;
    if(cnt[x]>=(B>>1)) big.insert(x);
    all.insert(cnt[x]);
    s[cnt[x]].insert(x);
    Update(cnt[x]);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    #define endl '\n'

    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];

    mx[n+1]=0,mn[n+1]=n+1;
    for(int i=1;i<=n;i++) cnt[a[i]]++;
    for(int i=1;i<=n;i++) s[cnt[i]].insert(i);
    for(int i=n;i>=0;i--) Update(i);
    for(int i=1;i<=n;i++) all.insert(cnt[i]);
    for(int i=1;i<=n;i++) if(cnt[i]>=(B>>1)) big.insert(i);

    while(q--){
        int i,x;
        cin>>i>>x;

        Veto(a[i]);
        a[i]=x;
        Vote(a[i]);

        int lim=*all.rbegin();
        if(lim<=B){
            int ans=0;
            for(int i=1;i<=lim;i++){
                ans=max(ans,mx[max(lim-i,1)]-mn[i]);
                ans=max(ans,mx[i]-mn[max(lim-i,1)]);
            }
            cout<<ans<<endl;
        }else{
            int ans=0;
            for(int i:big){
                ans=max(ans,mx[max(lim-cnt[i],1)]-i);
                ans=max(ans,i-mn[max(lim-cnt[i],1)]);
            }
            cout<<ans<<endl;
        }
    }

    return 0;
}