P9143 [THUPC 2023 初赛] 众数

Alex_Wei · 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;
}