自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:38:05，当前版本为作者最后更新于2022-05-08 22:27:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8330 [ZJOI2022] 众数

转化一下题意，求出将循环序列切成两段，每段区间众数出现次数之和的最大值。

一般 “出现次数” 都与 根号分治 挂钩，因为出现次数少的数可以直接考虑出现次数，出现次数多的数可以直接考虑每个数，这样就出现了根号。

将出现次数 $\geq B$ 的数成为大数，反之成为小数。

考虑大数在外侧的情况。枚举每个大数 $x$，先把所有 $x$ 选上，再考虑枚举内层的数 $y$，那么一段区间 $[l, r]$ 的贡献就是 $[l, r]$ 内 $y$ 的个数减去 $x$ 的个数。这是一个最大子段和问题。区间右端点必然可以调整至仅在 $y$ 出现的位置取到。

大数在内侧同理，只要先把所有 $y$ 选上，贡献取相反数即可。同理，此时区间右端点在 $y$ 出现的前一个位置取到。预处理 $[a_i = x]$ 的前缀和，这样对每个 $x$ 枚举所有 $y$ 的总复杂度就是线性，这部分是 $\dfrac {n ^ 2} B$。

接下来我们只关心小数配对小数的情况。如果确定了某个小数 $x$ 在外侧，那么容易证明内侧区间 $[l, r]$ 可以调整至满足 $l = 1$ 或 $a_{l - 1} = x$，且 $r = n$ 或 $a_{r + 1} = x$。这样一来，可能的内侧区间个数只有出现次数平方个。

这样我们只需求出区间 $[l, r]$ 的众数出现次数（甚至不需要具体值，因为最终内侧会变成外侧，也就是外侧的值才有用）。

普通地求 $q$ 次众数的时间复杂度是莫队或者分块的 $q\sqrt n$，放在本题肯定不行。

实际上还有一个性质没有用到，就是只需要众数出现次数 $\leq B$。我们对每个位置 $i$ 预处理出来使得 $[i, r]$ 的众数出现次数等于 $j$ 最小的 $r$（注意循环序列），记作 $p_{i, j}$。这个枚举出现次数然后 two-pointers。

这样查询区间 $[l, r]$ 的众数的时候只需要二分出现次数并判断是否有 $p_{l, mid} \leq r$ 即可在对数时间内求众数。可以通过 50pts。

更进一步地，考虑左端点 $l$ 固定，右端点右移的过程，$[l, r]$ 众数的出现次数一定不断增加。根据单调性用指针维护即可。对于每个左端点最多右移 $B$ 次右端点，而指针的移动次数均摊也是 $B$ 次，所以这部分时间复杂度 $\mathcal{O}(nB)$。

取 $B = \sqrt n$ 得到时空复杂度 $\mathcal{O}(n\sqrt n)$。注意大小为根号的那一维要放在前面，防止过多 cache miss（卡车丢失，大雾）导致 TLE。

• 一种空间复杂度线性的做法：考虑从左往右扫描线枚举右端点 $r$，时刻维护 $S_i$ 表示 $[i, r - 1]$ 的众数出现次数。跳过出现次数大于等于 $B$ 的 $a_r$。接下来讨论的 $a_r$ 的出现次数均小于 $B$。

  首先对于 $a_r$ 的所有出现位置 $l$，用 $l$ 之前 $a_r$ 的出现次数，加上 $r$ 之后 $a_r$ 的出现次数，加上 $S_{l + 1}$ 更新 $a_r$ 的答案。

  全部更新完毕后再将 $S_i$ 从 $[i, r - 1]$ 更新为 $[i, r]$，这部分可以再枚举 $a_r$ 的所有出现位置 $l$，用 $[l, r]$ 内 $a_r$ 的出现次数 $c$ 更新所有 $S_{1\sim l - 1}$。注意到 $S$ 的单调不增性，所以从 $l - 1$ 到 $1$ 枚举 $p$，一旦 $S_p\geq c$ 那么说明再往前更新也是无用的，可以 break 掉。

  由于每次 $p$ 向前移动都会使 $S$ 的总和至少增加 $1$，而 $S$ 的总和最终不超过 $nB$，所以总复杂度是线性根号。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
	int x = 0;
	char s = getchar();
	while(!isdigit(s)) s = getchar();
	while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
	return x;
}
const int B = 200;
const int N = 2e5 + 5;
int n, a[N], d[N], ans[N], pointer[B][N];
vector <int> pos[N];
void solve() {
	cin >> n;
	for(int i = 1; i <= n; i++) pos[i].clear(), ans[i] = 0;
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), d[i] = a[i];
	sort(d + 1, d + n + 1);
	for(int i = 1; i <= n; i++) pos[a[i] = lower_bound(d + 1, d + n + 1, a[i]) - d].push_back(i);
	for(int i = 1; i <= n; i++) {
		if(pos[i].size() < B) continue;
		static int pre[N];
		memset(pre, 0, sizeof(pre));
		for(int it : pos[i]) pre[it] = 1;
		for(int p = 1; p <= n; p++) pre[p] += pre[p - 1];
		for(int j = 1; j <= n; j++) {
			if(i == j) continue;
			int mx = 1, cur = 1;
			for(int ind = 1; ind < pos[j].size(); ind++) mx = max(mx, cur = max(1, cur - (pre[pos[j][ind]] - pre[pos[j][ind - 1]]) + 1));
			ans[i] = max(ans[i], mx + (int) pos[i].size());
			mx = cur = 0;
			for(int ind = 1; ind < pos[j].size(); ind++) {
				mx = max(mx, cur += pre[pos[j][ind]] - pre[pos[j][ind - 1]]);
				cur = max(0, cur - 1);
			}
			ans[j] = max(ans[j], mx + (int) pos[j].size());
		}
	}
	int limit = 0;
	for(int i = 1; i <= n; i++) limit = max(limit, (int) pos[i].size());
	limit = min(limit, B - 1);
	for(int i = 1; i <= limit; i++) {
		static int buc[N], mode;
		memset(buc, mode = 0, sizeof(buc));
		for(int l = 1, r = 0; l <= n; buc[a[l++]]--) {
			while(buc[mode] < i) {
				buc[a[r = r < n ? r + 1 : 1]]++;
				if(buc[a[r]] > buc[mode]) mode = a[r];
			}
			pointer[i][l] = r;
		}
	}
	for(int i = 1; i <= n; i++) {
		if(pos[i].size() > limit) continue;
		for(int j = 0; j < pos[i].size(); j++) { // 枚举左端点 l.
			for(int k = 1; k <= limit; k++) if(pointer[k][1] < pos[i][j]) ans[i] = max(ans[i], (int) pos[i].size() - j + k); // 先处理一下 l = 1 的情况.
			int pt = j, p = pos[i][j] + 1;
			if(p > n) continue;
			for(int k = 1; k <= limit; k++) { // 这里不同于题解的是, 我从小到大枚举出现次数, 用指针维护最小的合法右端点, 本质没有太大差别.
				if(pointer[k][p] < p) break; // 如果要绕过去变成外侧就不行了.
				while(pt < pos[i].size() && pos[i][pt] <= pointer[k][p]) pt++; // 出现次数增大使得右端点右移.
				ans[i] = max(ans[i], j + k + 1 + (int) pos[i].size() - pt);
			}
		}
	}
	int mx = 0;
	for(int i = 1; i <= n; i++) mx = max(mx, ans[i]);
	cout << mx << endl;
	for(int i = 1; i <= n; i++) if(ans[i] == mx) printf("%d\n", d[i]);
}
int main() {
	int T;
	cin >> T;
	while(T--) solve();
	return cerr << clock() << endl, 0;
}
/*
2022/5/8
start thinking at ??:??
高妙根号分治题.
先处理大块与大块和小块.
再处理小块之间的情况.
写一个 sqrt log 试试看.
又 T 又 WA, 我不理解.
start coding at 14:42
交换 N, B 两维跑得飞快啊.
实际上将 B 开小一点效率会比较高, 因为对于小数的处理用了巨大的二维数组, 实在是太慢了.
finish debugging at 16:21
*/