记录编号	600047	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO25 Open Gold]Election Queries	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	13.381 s
提交时间	2025-04-12 15:28:03	内存使用	10.66 MiB

#include<bits/stdc++.h>
using namespace std;
int main(){
	    freopen("Queries.in", "r", stdin);
	    freopen("Queries.out", "w", stdout);
  ios::sync_with_stdio(0);cin.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;
  for(int i:a) s[c[i]].insert(i),v.insert(c[i]);
  while(q--){
    int p,x; cin>>p>>x; p--,x--;
    int k=a[p];
    s[c[k]].erase(k);
    if(s[c[k]].empty()) v.erase(c[k]);
    s[--c[k]].insert(k);
    v.insert(c[k]);
    s[c[x]].erase(x);
    if(s[c[x]].empty()) v.erase(c[x]);
    s[++c[x]].insert(x);
    v.insert(c[x]);
    a[p]=x;
    vector<int> e(v.begin(),v.end());
    int r=0,mx=0;
    for(int i=0,j=e.size()-1;i<e.size();++i){
      if(!e[i]) continue;
      while(~j && e[j] && e[j]+e[i]>=e.back()) mx=max(mx,*s[e[j]].rbegin()),j--;
      r=max(r,mx-*s[e[i]].begin());
    }
    cout<<r<<'\n';
  }
}