题意：
给定一个长度为n的序列，求最长的满足区间众数有至少两种的区间长度。如果不存在这样的区间，输出 0。
两个版本，e a s y中1 < = a i < = 100,h a r d中1 < = a i < = n
思路：
一个很重要的性质：
记整段序列的众数为x,答案区间里x一定也是众数之一；
反证法：若当前答案区间里x出现的次数不是最多的，可以将区间向两边扩展，每次x 的数量都有可能增加1,所有会有某个时间段，x的出现次数跟最大的出现次数一样大，并且这段区间仍旧合法，并且比原先的区间更优，假设不成立。
由于e a s y版本中，1 < = a i < = 100，在确定了众数x后，我们可以枚举y表示让x跟y出现次数一样多的话能够扩展到的最长区间长度。每次枚举的时候，维护一个新的数组：将等于x的位置变为+ 1，将等于y的位置变为− 1，其他数则为0；问题就转化成了：给定一个序列，求最长的区间使得区间和为0;
维护一个前缀和，并用m a p记录一下前缀和为s u m的最小下标，再遇到s u m的话就取最大值维护答案；
时间复杂度为O ( 100 n )h a r d版本中，1 < = a i < = n ，继续采用上述算法复杂度为O ( n 2 ),考虑用根号分治思想平衡预处理跟询问。
记录每个数出现的次数c n t [ i ].对于c n t [ i ] > = n的数，继续采取上述算法，这样的数的个数不超过n，所以这部分的复杂度为O ( n n )
对于c n t [ i ] < = n的数，枚举出现次数z，假设出现次数为z的数可以作为众数，用双指针维护能够扩展到的最大区间。
如果这个序列有两个众数的话，答案就是n
代码：
D1
const int maxn=2e5+100; int n,a[maxn]; unordered_map<int,int>mp;//前缀和标记数组 int main(){ n=read; int res=0,cnt=0,pos; rep(i,1,n){ a[i]=read; mp[a[i]]++; if(res<mp[a[i]]){//记录众数 res表示众数出现的次数，pos表示众数，cnt表示众数的个数 res=mp[a[i]];pos=a[i];cnt=1; } else if(res==mp[a[i]]) cnt++; } if(cnt>1){ write(n); return 0; } int ans=0; for(int i=1;i<=100;i++){//枚举第二个数 if(i==pos) continue;//两者不能相等 mp.clear();mp[0]=0;//每次清空数组，注意有可能本身就是$0$ int sum=0; for(int j=1;j<=n;j++){ if(a[j]==i) sum--; else if(a[j]==pos) sum++; if(mp.count(sum)) ans=max(ans,j-mp[sum]);//以前出现过的话更新答案 else mp[sum]=j;//记录下标最小的位置 } } write(ans); return 0; }
D2
const int maxn=2e5+100; int n,a[maxn],cnt[maxn],ans=0,maxx; bool st[maxn]; //unordered_map<int,int>mp; int mp[maxn*2];//防止下标为负，整体偏移 void solve1(int x){ rep(i,1,n) mp[i]=mp[i+n]=-1; int sum=n;mp[n]=0,mp[0]=0; for(int i=1;i<=n;i++){ if(a[i]==maxx) sum++; else if(a[i]==x) sum--; if(mp[sum]!=-1) ans=max(ans,i-mp[sum]); else mp[sum]=i; } } void solve2(int x){ rep(i,1,n) mp[i]=0; int l=1,tot=0;//记录左端点，tot表示出现次数为x的数的个数 mp[a[l]]++; if(mp[a[l]]==x) tot++; rep(i,2,n){ mp[a[i]]++; if(mp[a[i]]==x) tot++;//更新tot else if(mp[a[i]]>x){ while(mp[a[i]]>x){//移动左端点直到区间合法 mp[a[l]]--; if(mp[a[l]]==x-1) tot--;//更新tot l++; } } if(tot>=2) ans=max(ans,i-l+1);//合法区间的判断 } } int main(){ n=read; rep(i,1,n){ a[i]=read; cnt[a[i]]++; if(cnt[maxx]<cnt[a[i]]) maxx=a[i]; } int m=sqrt(n); rep(i,1,n){ if(cnt[i]>=m&&!st[i]&&i!=maxx){//出现次数大于sqrtn的采取D1的写法 st[i]=1; solve1(i); } } for(int i=1;i<m;i++) solve2(i);//枚举次数 write(ans); return 0; }
