[THUSC 2019] 数列

Luogu

IDLGP10342

Time4000ms

Memory1024MB

DifficultyP6

2019THUSC

定义一个长度为 $k$ 的数列的价值为：$val = \max \limits_{1 \le i \le k}\{i \times f(i,k)\}$。其中 $f(i,j)$ 表示区间 $[i,j]$ 范围内数值种类数。给出一个长度为 $n$ 的数列，计算所有连续子区间的价值总和。将一个连续子区间视为一个独立的数列，计算出的价值即为该连续子区间的价值。设 $m$ 为数列里出现的数值种类数。 ## Input 第一行输入一个整数 $n$。第二行输入 $n$ 个正整数，$a_1, a_2, \dots, a_n$ 描述数列里每个位置上的数值。对于所有的输入数据，都满足 $1\le n \le 10^5$。 ## Output 第一行输出一个整数表示答案对 $998\ 244\ 353$ 取模。 [samples] ## Note **【样例解释 1】** 所有长度为 $1$ 的区间对答案的贡献都是 $1$。所有长度为 $2$ 的区间对答案的贡献都是 $2$。 $[1,3]$ 这个区间对答案贡献为 $3$。 $[2,4]$ 这个区间对答案贡献为 $4$。 $[1,4]$ 这个区间对答案贡献为 $6$。综上答案为 $ans = 4 \times 1 + 2 \times 3 + 3 + 4 + 6 = 23$。 **【样例 2】** 见题目附件 `2.in/ans` **【样例 3】** 见题目附件 `3.in/ans` **【样例 4】** 见题目附件 `4.in/ans` **【样例 5】** 见题目附件 `5.in/ans` **【子任务】** | 子任务编号 | $n\le$ | $m\le$ | $a_i\le$ | 约束 | 分值 | | :--: | :--: | :--: | :--: | :--: | :--: | | 1 | $800$ | $800$ | $10^5$ | 无 | 13 | | 2 | $10^5$ | $10^5$ | $10^5$ | 不会出现相同的数值 | 15 | | 3 | $8\times 10^4$ | $600$ | $10^5$ | $[1,m][m+1,2m]\dots[\lfloor\frac{n}{m}\rfloor\times m + 1,n]$每个区间无重复数值 | 21 | | 4 | $10^5$ | $80$ | $10^5$ | 无 | 24 | | 5 | $8\times 10^4$ | $600$ | $10^5$| 无 | 27 |

Samples

Input #1

4
12 23 23 45

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[THUSC 2019] 数列",
    "description": {
      "content": "定义一个长度为 $k$ 的数列的价值为：$val = \\max \\limits_{1 \\le i \\le k}\\{i \\times f(i,k)\\}$。 其中 $f(i,j)$ 表示区间 $[i,j]$ 范围内数值种类数。 给出一个长度为 $n$ 的数列，计算所有连续子区间的价值总和。将一个连续子区间视为一个独立的数列，计算出的价值即为该连续子区间的价值。 设 $m$ 为数列里出现的数值种类",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10342"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "定义一个长度为 $k$ 的数列的价值为：$val = \\max \\limits_{1 \\le i \\le k}\\{i \\times f(i,k)\\}$。\n\n其中 $f(i,j)$ 表示区间 $[i,j]$ 范围内数值种类数。\n\n给出一个长度为 $n$ 的数列，计算所有连续子区间的价值总和。将一个连续子区间视为一个独立的数列，计算出的价值即为该连续子区间的价值。\n\n设 $m$ 为数列里出现的数值种类...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments