求 max（区间不同数的个数-区间mex）

rt

做法：

1. 先枚举\(mex\)，说明\(mex\)不会在答案区间中存在
2. 那么答案区间就是一个不包含\(mex\)的极长区间，可能有\(n\)个
3. 一个区间中不同数的个数可以用树状数组求：维护以下标为权值的桶，每次更新last数组

const int M=5e5+5;
int sum[M];
int lowbit(int p){return p&-p;}
void add(int p,int x){while(p<=M){sum[p]+=x;p+=lowbit(p);}
}
int qr(int x){int res=0;while(x){res+=sum[x];x-=lowbit(x);}return res;
}
int qr(int l,int r){return qr(r)-qr(l-1);
}
int n,m;
void solve(){cin>>n>>m;vector<int>a(n+1);rep(i,1,n)cin>>a[i];map<int,int>last;int ans=-1;rep(i,1,n){if(last[a[i]]){add(last[a[i]],-1);}int temp=last[a[i]];ans = max(ans, qr(temp+1,i-1)-a[i]);last[a[i]]=i;add(i,1);}rep(i,1,n+1){ans= max(ans, qr(last[i]+1,n)-i);}for(auto[x,y]:last){if(y!=0)add(y,-1);}cout<<ans<<endl;
}