赛时不会某个结论，被

下文认为 $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;
}