# 众数 II## 题目背景dXqwq 是一个不可爱的男孩子。他在 NOI2022 中的众数一题定义了 $10^6$ 个 stddeque 并成功 MLE。## 题目描述给定一个长度为 $n$ 的序列 $a$我们通过以下方式构造序列 $b$：- 初始时 $b$ 为空序列。- 对于 $i=12cdotsn$我们依次向 $b$ 的尾部插入 $12cdotsa_i$。dXqwq 定义一个序列的最小众数为

解题思路

首先，我们可以观察到，$b$ 的每个子区间的最小众数的和与 $a$ 的值有关。具体来说，对于 $a$ 中的每个数 $a_i$，如果我们知道 $b$ 中以 $a_i$ 为最小众数的子区间的个数为 $x$，那么 $a_i$ 在 $b$ 的每个子区间的最小众数的和中的贡献就是 $a_i \times x$。因此，我们的目标是求出 $a$ 中每个数的贡献，并将它们相加。

接下来，我们考虑如何求出以 $a_i$ 为最小众数的子区间的个数 $x$。观察一下可以发现，$a_i$ 为最小众数的子区间的个数与 $a_i$ 的出现次数有关，具体地说，$a_i$ 为最小众数的子区间的个数等于 $a_i$ 的出现次数乘以 $a_i$ 在 $a$ 中的位置的范围。我们可以通过遍历 $a$ 来统计 $a_i$ 的出现次数，并使用一个辅助数组 $p$ 来记录 $a_i$ 在 $a$ 中的位置范围。

最后，我们只需要将每个数的贡献相加，并对 $998244353$ 取模即可得到答案。

算法步骤

1. 读取输入，初始化变量。
2. 遍历 $a$，统计每个数的出现次数，并更新 $p$ 数组。
3. 遍历 $a$，计算每个数的贡献，并累加到答案中。
4. 对答案取模，并输出。

代码实现

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<long long> cnt(n + 1, 0);
    vector<long long> p(n + 1, 0);

    for (int i = 0; i < n; i++) {
        cnt[a[i]]++;
        if (p[a[i]] == 0) {
            p[a[i]] = i + 1;
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 0) {
            continue;
        }
        long long x = cnt[i] * (cnt[i] + 1) / 2;
        long long y = (n - p[i] + 1) * (p[i] - 1) + 1;
        ans = (ans + i * x % MOD * y % MOD) % MOD;
    }

    cout << ans << endl;

    return 0;
}

复杂度分析

该算法需要遍历输入数组 $a$ 两次，因此时间复杂度为 $O(n)$。

空间复杂度为 $O(n)$，用于存储变量 $cnt$ 和 $p$。

总结

本题通过观察，将问题转化为求每个数的贡献，并使用辅助数组记录每个数的出现次数和位置范围，最后将贡献相加即可。这是一道较为简单的数学问题，需要观察和分析