[USACO25OPEN] Election Queries G 题解

· · 题解

赛时不会某个结论，被 @V 赖摇斑炸鱼佬 嘲讽了。

下文认为 n,q 同阶。

令奶牛 x 的得票数为 c_x，记 \mathrm{mx}=\max\limits_{i=1}^n c_i。显然两头奶牛 x,y 能当选的充要条件为 c_x+c_y\ge\mathrm{mx}。

考虑一种 O(n^2) 做法：对于每种 c 的值 v，找出最小和最大的 i 满足 c_i=v，枚举其中一个出现次数 c_x，找出 c_x 对应的最小的 x_{\min}，使用双指针找出 c_y\ge\mathrm{mx}-c_x 中的 y_{\max}，将所有情况取最大值即为答案。需要用到的值都可以用 set 维护。

赛时卡在这一步了，但事实上上面的做法离正解就差一个十分关键的结论：若一个正整数序列 a 满足 \sum a_i\le S，那么 a 中元素的种类数的量级是 O(\sqrt{S}) 的。证明考虑如何卡满到这个上界，只需要构造 1,2,3,\ldots 即可。由于 \sum c_i=n，所以 c_i 的值只有本质不同的 O(\sqrt{n}) 种。

于是对于上面的暴力做法，如果只考虑至少对应着一个 x 的 c_x，时间复杂度就是 O(n\sqrt{n}) 的。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,q; cin>>n>>q;
  vector<int> a(n),c(n);
  for(auto &i:a)cin>>i,c[--i]++;
  vector<set<int> > s(n+1); set<int> v;
  // s 是每个 c 对应着那些 x
  // v 是至少对应着一个 x 的 c 的集合
  for(int i:a)s[c[i]].emplace(i),v.emplace(c[i]);
  while(q--){
    int p,x,r=0; cin>>p>>x,p--,x--;
    s[c[a[p]]].erase(a[p]);
    s[c[x]].erase(x);
    if(s[c[a[p]]].empty())v.erase(c[a[p]]);
    if(s[c[x]].empty())v.erase(c[x]);
    s[--c[a[p]]].emplace(a[p]);
    s[++c[x]].emplace(x);
    v.emplace(c[a[p]]),v.emplace(c[x]),a[p]=x;
    vector<int> e(v.begin(),v.end());
    for(int i=0,p=e.size()-1,mx=0;i<e.size();i++)
      if(e[i]){
        while(p>=0&&e[p]&&e[p]+e[i]>=e.back())
          mx=max(mx,*prev(s[e[p]].end())),p--;
        r=max(r,mx-*s[e[i]].begin());
      } // 双指针求解过程
    cout<<r<<'\n';
  }
  return 0;
}