「EZEC-14」众数 II

Luogu

IDLGP9461

Time1000ms

Memory512MB

DifficultyP5

洛谷原创O2优化洛谷月赛链表单调栈

给定一个长度为 $n$ 的序列 $a$，我们通过以下方式构造序列 $b$： - 初始时 $b$ 为空序列。 - 对于 $i=1,2,\cdots,n$，我们依次向 $b$ 的尾部插入 $1,2,\cdots,a_i$。 dXqwq 定义一个序列的**最小众数**为所有出现次数最大的数的最小值。例如 $[1,1,4,5,1,4]$ 的最小众数为 $1$，而 $[1,14,5,14,19,19,8,10]$ 的最小众数为 $14$。你需要求出 $b$ 的每个子区间的**最小众数**的和。由于答案可能很大，你只需要输出它对 $998244353$ 取模后的值。 ## Input 第一行输入一个整数 $n$。第二行输入 $n$ 个整数 $a_i$。 ## Output 输出一个整数，代表 $b$ 的每个子区间的最小众数的和对 $998244353$ 取模的值。 [samples] ## Background dXqwq 是一个不可爱的男孩子。他在 NOI2022 中的众数一题定义了 $10^6$ 个 ``std::deque`` 并成功 MLE。 ## Note **【样例解释】** 在第一个样例中，$b=[1,1,2,1,2,3]$。有 $15$ 个区间的最小众数为 $1$，$5$ 个区间的最小众数为 $2$，$1$ 个区间的最小众数为 $3$，因此答案为 $15\times 1+5\times 2+1\times 3=28$。 **【提示】** 开 $10^6$ 个 ``std::deque`` 在空间限制为 512MB 时一定会 MLE。 **【数据范围】** **本题采用捆绑测试。** - Subtask 1（10 pts）：$\sum a_i\leq 100$。 - Subtask 2（20 pts）：$\sum a_i\leq 10^3$。 - Subtask 3（20 pts）：$\sum a_i\leq 10^6$。 - Subtask 4（10 pts）：$n\leq 2$。 - Subtask 5（20 pts）：$n\leq 10^3$。 - Subtask 6（10 pts）：$a_i\leq 2$。 - Subtask 7（10 pts）：无特殊限制。对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$1\leq a_i\leq 10^6$。

Samples

Input #1

3
1 2 3

Output #1

Input #2

9
9 9 8 2 4 4 3 5 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "「EZEC-14」众数 II",
    "description": {
      "content": "给定一个长度为 $n$ 的序列 $a$，我们通过以下方式构造序列 $b$： - 初始时 $b$ 为空序列。 - 对于 $i=1,2,\\cdots,n$，我们依次向 $b$ 的尾部插入 $1,2,\\cdots,a_i$。 dXqwq 定义一个序列的**最小众数**为所有出现次数最大的数的最小值。例如 $[1,1,4,5,1,4]$ 的最小众数为 $1$，而 $[1,14,5,14,19,19,8",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9461"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的序列 $a$，我们通过以下方式构造序列 $b$：\n\n- 初始时 $b$ 为空序列。\n- 对于 $i=1,2,\\cdots,n$，我们依次向 $b$ 的尾部插入 $1,2,\\cdots,a_i$。\n\ndXqwq 定义一个序列的**最小众数**为所有出现次数最大的数的最小值。例如 $[1,1,4,5,1,4]$ 的最小众数为 $1$，而 $[1,14,5,14,19,19,8...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments