专栏文章

题解：P8330 [ZJOI2022] 众数

DDanslapiscine
P8330题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq8ydd7
此快照首次捕获于
2025/12/04 00:54
3 个月前
此快照最后确认于
2025/12/04 00:54
3 个月前
查看原文
根号分治大成题。蒟蒻不看题解想了一天。
题目意思就是在序列中删掉一区间，分别取剩下的段和删掉的段中的众数的个数，问他们的和最大能为多少，还有能取到最大和的剩下那段众数的方案。
直接做是不行的，用根号分治的方法创造条件。

1. 处理小于 n\sqrt{n} 个数字。

这种情况容易想到对每个数字分开处理，花费 O(n)O(n) 的时间。
设处理到的数字是 ii。可以想到对于该数在区间内的情况，若外面选的数字是 jj，我们把数组中 ii 看作 +1+1，jj 看作 −1-1，发现答案就是一段区间的和加上数组中 jj 的个数。做前缀和，需要查询历史最小值，发现可以维护。
对于该数在区间外面的情况，可设 fjf_j 表示当前区间内选 jj 最大取到多少个数，发现也可以维护。
这样我们可以处理较大的 n\sqrt{n} 个数，剩下的数就出现次数只小于等于 n\sqrt{n}。

2. 每个数字出现次数小于等于 n\sqrt{n}。

发现区间内和区间外的众数个数均小于等于 n\sqrt{n} ，对每个点去求若作为左端点，那么右端点至少是几，区间内众数为 ss。然后显然可以用双指针求解。
因为众数个数随区间长度增加单调递增，所以可以从后往前求解，设当前点为 ii，那么用大于 ii 的点 jj ，且 ai=aja_i=a_j 的点更新即可。
时间复杂度 O(nn)O(n \sqrt{n} )。我的写法细节巨多。
CPP
#include <bits/stdc++.h>
using namespace std;

int TAT;
int n, parter, a[500002], nn, aa[500002], cnt[500002];
int Ans, haveAns[500002];
void update(int s,int num){
	if(s > Ans) Ans = s, haveAns[num] = Ans;
	else if(s == Ans) haveAns[num] = Ans;
}

int adder, have[500002], Max[500002];
int f[500002];
void solve1(){
	for(int i=1;i<=nn;i++){
		if(cnt[i] <= parter) continue;
		
		// 把i看成1，把a[j]看成-1，前缀和have[a[j]]
		// 全局加1   单点-1   查询单点历史最小值 
		for(int j=1;j<=nn;j++) have[j] = 0, Max[j] = 0;
		adder = 0;
		for(int j=1;j<=n-1;j++){
			if(a[j] == i) adder++;
			have[a[j]]--, Max[a[j]] = max(Max[a[j]], -have[a[j]]-adder);
			update(cnt[a[j+1]]+have[a[j+1]]+adder+Max[a[j+1]], a[j+1]);
		}// 在内
		
		adder = 0;
		for(int j=1;j<=nn;j++) f[j] = 0;
		for(int j=1;j<=n;j++){
			if(a[j] == i) adder++;
			f[a[j]] = max(f[a[j]] + 1, adder + 1);
			update(f[a[j]] + cnt[i] - adder, i);
		}// 在外 
	}
}

int head[500002], nxt[500002], zhong[500002];
void solve2(){
	for(int i=1;i<=nn;i++) head[i] = n+1;
	nxt[n+1] = 0;
	for(int i=1;i<=n;i++) zhong[i] = n+1;
	for(int i=n;i>=1;i--){
		if(cnt[a[i]] <= parter) {
			nxt[i] = head[a[i]], head[a[i]] = i;
		}
	}
	for(int i=n;i>=1;i--){
		if(cnt[a[i]] > parter) continue;
		
		int cnt2 = 0;
		for(int pos1=nxt[i],cnt1=0;pos1;pos1=nxt[pos1],cnt1--){
			while(cnt2 + 1 <= parter && zhong[cnt2+1] < pos1) cnt2++;
			update(cnt[a[i]]+cnt1+cnt2,a[i]);
		}
		
		for(int j=i,k=1;j!=n+1;j=nxt[j],k++){
			zhong[k] = min(zhong[k], j);
		}
	}
}

int main(){
	//freopen("mode_ex2.in","r",stdin);
	//freopen("zzz.out","w",stdout);
	
	scanf("%d",&TAT);
	
	while(TAT--){
		Ans = 0;
		for(int i=1;i<=n;i++) haveAns[i] = 0;
		
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]), aa[i] = a[i];
		sort(aa+1,aa+n+1), nn = unique(aa+1,aa+n+1)-aa-1;
		for(int i=1;i<=nn;i++) cnt[i] = 0;
		for(int i=1;i<=n;i++) a[i] = lower_bound(aa+1,aa+nn+1,a[i])-aa, cnt[a[i]]++;
		
		parter = sqrt(n);
		solve1();
		reverse(a+1,a+n+1);
		solve1();
		
		solve2();
		reverse(a+1,a+n+1);
		solve2();
		
		printf("%d\n",Ans);
		for(int i=1;i<=nn;i++) {
			if(haveAns[i] == Ans) printf("%d\n",aa[i]);
		}
	}
	
	return 0;
}

/*
1
6
2 4 2 4 8 8

8 8 4 2 4 2
*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...