记录编号	600877	评测结果	AAAAAAAAAAAAAAA
题目名称	4133.[USACO25 Open Gold]Election Queries	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	11.692 s
提交时间	2025-05-20 15:52:13	内存使用	18.75 MiB

#include <iostream>     
#include <cstdio>       
#include <map>          
#include <set>          
#include <cstring>    
//#define int long long  
using namespace std;

const int N = 2e5+10;

map<int,int>mp;

set<int>f[N];

int n,q,a[N],m[N],d[2020],mi[2020],mx[2020],cnt,ans,k;

//void upd(int x,int n){
//	mp[m[x]]--;if(!mp[m[x]])mp.erase(m[x]);
//	f[m[x]].erase(x),m[x]+=n,mp[m[x]]++,f[m[x]].insert(x);
//}

void upd(int x,int v){
    mp[m[x]]--;
    if(!mp[m[x]]){
	mp.erase(m[x]);
    	
	}
    f[m[x]].erase(x);
    m[x]+=v;
    mp[m[x]]++;
    f[m[x]].insert(x);
}

signed main(){
	freopen("Queries.in","r",stdin);
	freopen("Queries.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        m[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        mp[m[i]]++;
        f[m[i]].insert(i); 
    }
    while(q--){
        int ii,x;
        scanf("%d%d",&ii,&x);
        upd(a[ii],-1);
        a[ii]=x;
        upd(a[ii],1);
        memset(d,0,sizeof(d));
        memset(mi,0,sizeof(mi));
        memset(mx,0,sizeof(mx));
        cnt=ans=0;
        for(auto u:mp){
            if(u.first){
                d[++cnt]=u.first;
            }
        }
        k=d[cnt];
        for(int i=1;i<=cnt;i++){
            mi[i]=*f[d[i]].begin();
            mx[i]=*f[d[i]].rbegin(); 
        }
        for(int i=cnt-1;i;i--){
            mx[i]=max(mx[i],mx[i+1]);
        }
        for(int l=1,r=cnt;l<=cnt;l++){
            while(r-2>=0&&d[r-1]+d[l]>=k){
                r--;
            }
            ans=max(ans,mx[r]-mi[l]);
        }
        printf("%d\n",ans);
    }
    return 0;
}