[ZJOI2022] 众数题解
Cherished
·
·
题解
为了象征性的证明自己没有摆烂，所以来写题解了。感觉这还算是一道比较传统的题目吧，虽然我可能想了一个半小时才做出来，但是做出来之后又感觉好像不是很难。
简要题意
给你一个长度为 n 的数列，你可以给其中的任意一个连续段加上任意大的一个数，问修改完之后数列的众数最多出现了多少次，并输出哪些数可以达到这个出现次数。
数据范围
多测！！！
### 解题思路
首先可以发现我们完全可以暴力枚举两个数，计算更改其中一个数之后，另一个数最多出现多少次。那么我们在这个说这个叫做被更改的数对统计答案的数的贡献。
显然我们只需要暴力计算出任意两个数的贡献就可以得到一个多项式的做法。
我们具体思考一下应该怎么做：假如是 $1$ 对 $2$ 做贡献，我们定义两个数组 $s1,s2$ 分别表示 $1$ 和 $2$ 个数的前缀和。此时可以发现我们的答案就是 $max_{r=1}^{n}{max_{l=1}^{r}{(s2_n-s2_r+s2_{l-1}+s1_r-s1_{l-1})}}$。
对于上面的式子我们显然可以把它变成 $s2_n+max_{r=1}^{n}{max_{l=1}^{r}{((-s2_r+s1_r)+(s2_{l-1}-s1_{l-1}))}}$，这样我们只需要对 $s2_{l-1}-s1_{l-1}$ 记录一个前缀 $min$ 就可以 $O(n)$ 的计算两个数的贡献了。
这样的时间复杂度是 $O(n^3)$，但是我们可以发现其实 $2$ 这个数是谁是完全无关紧要的，我们完全可以利用 $O(n)$ 的时间计算出来一个数对于所有数的贡献，这样我们的时间复杂度就变成了 $O(n^2)$。
毕竟是数据结构题而且还是众数，我们肯定会往根号的方向上去想的（接下来我们用 $B$ 代表 $\sqrt{n}$），可以发现大于 $B$ 的数只有 $\frac{n}{B}$ 种，完全可以解决一个大数对其他数的贡献。（我们之后管大于 $B$ 的数叫大数，小于等于 $B$ 的数叫小数）。
显然之后只需要思考一个小数对其他数的贡献就行了。
之后我的做法可能就略微有一点麻烦了：
先考虑一个小数对一个小数的贡献：
我们从左往右扫，把当前点叫做 $i$。以 $i$ 为右端点，对于所有的点记录以这个点为左端的的众数出现次数。这样每次查询 $i$ 的贡献的时候，我们暴力枚举和 $i$ 权值相同的点 $j$。那么如果我们修改 $j$ 到 $i$ 中间的一段贡献就是 $i$ 之后和 $j$ 之前和 $i$ 相同的点的个数加上 $j$ 到 $i$ 这一段的众数出现次数，因为每个数最多只有 $B$ 个所以每次最多只会枚举 $B$ 次，这样枚举的时间复杂度就是 $nB$ 的了。
但是现在还有一个问题就是如何维护以每个点为左端点的众数个数，可以发现我们的每一次修改也是找到所有的 $j$，然后区间给一个前缀取 $max$，显然如果直接取 $max$ 我们就会多一个 $\log$ 这样是不能接受的。那么我们可以考虑，这里面维护的每一个众数个数的大小最多只有 $B$，而且它一定是从左到右递减的，这样的话我们每次修改其实可以直接暴力改，如果上一个点可以改就跳到上一个点，如果再上一个点还可以改，就继续跳。可以发现总修改次数是 $n$ 乘每个左端点众数次数最大值的也就是 $B$，这样我们的修改次数也是 $nB$ 的了。
之后我们再考虑一个小数对一个大数的贡献：
显然这回我们统计答案的时候就不能暴力的找到每一个 $j$ 了，但是我们可以发现你以这个点为右端点，所有左端点的众数出现次数最大只有 $B$，所以我们可以只维护当众数出现次数是 $B$ 的时候，左端点的最大值可以是多少。这样我们只需要对于每一个大数记录一个前缀和然后枚举中间修改的数的个数。这样查贡献的时间复杂度就是 $O(nB)$ 的了。至于如何维护这个左端点的最大值就非常的简单了。还是可以考虑暴力枚举 $j$ 直接修改就行了。
这样总时间复杂度就可以做到 $O(n\sqrt{n})$ 了。
### 关于代码
身为一道数据结构题没有卡常还是非常的良心的。
代码不是特别长，也比较好写，我写出来都没有调就过了（或许是数据太水了）。
下面是代码：
```cpp
const int N = 2e5 + 10;
int n, a[N], b[N], c, ct[N], B, ans[N], mx[N], s[N], lst[N], fir[N], k[N], rk[N];
int pre[500][N];
void calc1(int col) {
for (int i = 1; i <= n; i++) mx[i] = s[i] = 0;
int nw = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == col) nw++;
else {
ckmax(ans[a[i]], ct[a[i]] - s[a[i]] + nw + mx[a[i]]);
s[a[i]]++, ckmax(mx[a[i]], s[a[i]] - nw);
}
}
for (int i = 1; i <= c; i++) ckmax(ans[i], nw + mx[i]);
}
void solve() {
scanf("%d", &n), c = 0;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), b[++c] = a[i];
sort (b + 1, b + c + 1);
c = unique (b + 1, b + c + 1) - b - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + c + 1, a[i]) - b;
B = sqrt(n); int mxc = 0, crk = 0;
for (int i = 1; i <= c; i++) ct[i] = 0;
for (int i = 1; i <= n; i++) ckmax(mxc, ++ct[a[i]]);
for (int i = 1; i <= c; i++) ans[i] = mxc, rk[i] = 0;
for (int i = 1; i <= c; i++)
if (ct[i] > B) calc1(i), rk[i] = ++crk;
for (int i = 1; i <= crk; i++)
for (int j = 1; j <= n; j++)
pre[i][j] = pre[i][j - 1] + (rk[a[j]] == i);
for (int i = 1; i <= n; i++) lst[i] = fir[i] = k[i] = 0;
for (int i = 1; i <= n; i++) {
if (ct[a[i]] <= B) {
lst[i] = fir[a[i]], fir[a[i]] = i;
for (int o = 1, j = fir[a[i]]; j; o++, j = lst[j])
ckmax(k[o], j);
}
else {
for (int o = 1; k[o] && o <= B; o++)
ckmax(ans[a[i]], ct[a[i]] - pre[rk[a[i]]][i - 1] + o + pre[rk[a[i]]][k[o] - 1]);
}
}
for (int i = 1; i <= c; i++) if (ct[i] > B)
for (int o = 1; k[o] && o <= B; o++)
ckmax(ans[i], o + pre[rk[i]][k[o] - 1]);
for (int i = 1; i <= n; i++) lst[i] = fir[i] = k[i] = s[i] = 0;
for (int i = 1; i <= n; i++) {
if (ct[a[i]] <= B) {
s[i] = s[fir[a[i]]] + 1;
for (int j = fir[a[i]]; j; j = lst[j])
ckmax(ans[a[i]], ct[a[i]] - s[i] + 1 + s[j] + k[j + 1]);
ckmax(ans[a[i]], ct[a[i]] - s[i] + 1 + k[1]);
lst[i] = fir[a[i]], fir[a[i]] = i;
for (int o = 1, j = fir[a[i]]; j; o++, j = lst[j]) {
int tmp = j;
while (tmp > 0 && k[tmp] < o) k[tmp--] = o;
}
}
}
for (int i = 1; i <= c; i++) if (ct[i] <= B)
for (int j = fir[i]; j; j = lst[j]) {
if (j == n) continue;
ckmax(ans[i], s[j] + k[j + 1]);
}
int as = 0; vector<int> out;
for (int i = 1; i <= c; i++) {
if (as < ans[i]) out.clear(), out.push_back(b[i]), as = ans[i];
else if (as == ans[i]) out.push_back(b[i]);
}
printf("%d\n", as);
sort (out.begin(), out.end());
for (int x : out) printf("%d\n", x);
}
int T;
int main() {
for (scanf("%d", &T); T; T--) solve();
return 0;
}
```