正题

题目链接:https://www.luogu.com.cn/problem/P8330

题目大意

给出一个长度为\(n\)的序列\(a\)，你可以选择其中一个区间将其加上任意整数，要求这个序列的众数出现次数最多。

输出最多次数和可能的众数。

\(1\leq n\leq 2\times 10^5,1\leq a_i\leq 10^9,\sum n\leq 5\times 10^5\)，保证不所有数都相等。

解题思路

相当于找到一个区间使得区间外和区间内的众数次数和最大。

这个和出现次数挂钩，考虑根号分治。对于出现次数大于\(\sqrt n\)的数字，这种数字不会超过\(\sqrt n\)个，可以考虑对每个数字暴力做。

假设在区间外的数字是\(x\)，区间内的是\(y\)，那么我们区间中每个\(x\)会令答案\(-1\)，每个\(y\)会令答案\(+1\)。将\(x\)的位置视为\(-1\)，\(y\)的位置视为\(1\)，那么最大答案就是\(x\)的出现次数加最大子段和。

这个复杂度可以做到\(min(c_x,c_y)\)，其中\(c_x\)表示\(x\)的出现次数。

那对于每个\(c_x>\sqrt n\)的我们都可以\(O(n)\)解决它在外或者在内的情况。

然后考虑\(c_x\leq \sqrt n\)且\(c_y\leq \sqrt n\)的情况，先把所有\(c_x>\sqrt n\)的\(x\)给去掉，此时注意到任何区间的众数个数都是\(\leq \sqrt n\)的，那么我们预处理出\(f_{l,i}\)表示一个最小的\(r\)，满足\([l,r]\)的众数出现次数为\(i\)，这样我们对于每个在外面的\(x\)枚举两个\(x\)的位置作为端点，然后单指针移动计算他们之间区间的众数出现次数即可。

时间复杂度：\(O(n\sqrt n)\)

解题思路

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=2e5+10,M=450;
int n,T,a[N],b[N],r[N][M],s[N];
vector v[N],pr[N];
int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void calc(int x,int y){
	int ans1=0,ans2=0,now1=0,now2=0,las=0;
	for(int i=0;iT){
				for(int i=1;i<=n;i++)s[i]=0;
				for(int i=0;i=1;i--)
			for(int j=0;jn)break;
						while(z=1;i--)
			if(pr[i].size()){ans=i;break;}
		printf("%d\n",ans);
		sort(pr[ans].begin(),pr[ans].end());
		printf("%d\n",b[pr[ans][0]]);
		for(int i=1;i