自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:45:46，当前版本为作者最后更新于2023-03-11 10:59:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P9143 [THUPC 2023 初赛] 众数

考虑最终序列的形式。一个自然的想法是不断从 $n$ 摆到 $1$，如果没有这个数就跳过。

正确性证明：考虑众数序列 $m_1\sim m_S$，根据众数定义，其中只能有不超过 $\sum_{i = 1} ^ n\min(a_i, a_n)$ 个 $n$，只能有不超过 $\sum_{i = 1} ^ n \min(a_i, \max(a_{n - 1}, a_n))$ 个 $n - 1$ 或 $n$。以此类推，只能有不超过 $\sum_{i = 1} ^ n \min(a_i, \max_{j = p} ^ n a_j)$ 个不小于 $p$ 的数。而不断从 $n$ 摆到 $1$ 的序列恰好达到了所有上界。$\square$

接下来考虑贡献。考虑一个数 $i$ 被第 $j$ 次放入序列，那么它对应的众数为最大的 $p$ 使得 $a_p \geq j$。因此，设 $f_j$ 表示最大的 $p$ 使得 $a_p \geq j$，则 $a_i$ 的贡献为 $\sum_{j = 1} ^ {a_i} f_j$。前缀和即可。

时间复杂度 $\mathcal{O}(n + a)$。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
long long n, ans, a[N], f[N];
int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = n, mx = 0; i; i--) {
    while(mx < a[i]) mx++, f[mx] = f[mx - 1] + i;
    ans += f[a[i]];
  }
  cout << ans << "\n";
  return 0;
}