「SMOI-R1」Game

Luogu

IDLGP10407

Time1000ms

Memory512MB

DifficultyP5

动态规划 DP单调队列

在这个游戏里，一开始有 $n$ 个病毒，每个病毒的危害值为 $1$。每隔一段时间，病毒就会变异，会分裂成两个病毒，右边的病毒会比左边的病毒危害值多 $1$，变异过的病毒不会再变异。每个病毒有个变异极限 $b_i$，当这个病毒变异到 $b_i$ 时，这个病毒就会停止变异。也就是说，第 $i$ 个病毒最后都会分裂成一个危害值为 $\{1,2,3,\ldots,b_i\}$ 的病毒序列，当所有病毒变异完时，游戏开始，最终变异完的序列是 $\{1,2,3,\ldots,b_1,1,2,3,\ldots,b_2,\ldots,1,2,3,\ldots,b_n\}$。每次游戏，系统会选择一个区间，myz 需要把这个区间的病毒全部杀死，如果这个区间内的病毒的危害值的最大值是 $x$，那么 myz 需要花费 $x$ 的能量才能消灭它们。因为不知道系统会选择哪个区间，myz 想知道每个区间需要消耗的**能量值之和**。由于答案太大了，myz 想让你把答案对 $998244353$ 取模。 ## Input 第一行有一个整数 $n$，表示最开始有 $n$ 个病毒。第二行有 $n$ 个整数，第 $i$ 个整数是 $b_i$，表示第 $i$ 个病毒的变异上限。 ## Output 一个整数，表示 myz 需要消耗的能量值之和，答案对 $998244353$ 取模。 [samples] ## Background myz 很喜欢玩一款病毒游戏。 ## Note ### 样例解释第一个样例，病毒最后分裂成 $\{1,2,1,2,3\}$，区间 $[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[2,3],[2,4],[2,5],[3,3],[3,4],[3,5],[4,4],[4,5],[5,5]$ 的最小代价和就是 $1+2+2+2+3+2+2+2+3+1+2+3+2+3+3=33$。 ### 数据范围 **本题采用捆绑测试**。 subtask 编号|$n\leq$|$b_i\leq$|特殊性质|分值 -|-|-|-|- $1$|$10^2$|$10^2$|无|$20$ $2$|$10^4$|$10^2$|无|$20$ $3$|$10^6$|$10^9$|A|$20$ $4$|$10^6$|$10^9$|无|$40$ **特殊性质 A**： $b_1 \leq b_2 \leq \ldots \leq b_n$。对于 $100\%$ 的数据，保证 $1\le n\le10^6$，$1\le b_i\le 10^9$。

Samples

Input #1

2
2 3

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「SMOI-R1」Game",
    "description": {
      "content": "在这个游戏里，一开始有 $n$ 个病毒，每个病毒的危害值为 $1$。 每隔一段时间，病毒就会变异，会分裂成两个病毒，右边的病毒会比左边的病毒危害值多 $1$，变异过的病毒不会再变异。 每个病毒有个变异极限 $b_i$，当这个病毒变异到 $b_i$ 时，这个病毒就会停止变异。也就是说，第 $i$ 个病毒最后都会分裂成一个危害值为 $\\{1,2,3,\\ldots,b_i\\}$ 的病毒序列，当所有病",
      "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": "LGP10407"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在这个游戏里，一开始有 $n$ 个病毒，每个病毒的危害值为 $1$。\n\n每隔一段时间，病毒就会变异，会分裂成两个病毒，右边的病毒会比左边的病毒危害值多 $1$，变异过的病毒不会再变异。\n\n每个病毒有个变异极限 $b_i$，当这个病毒变异到 $b_i$ 时，这个病毒就会停止变异。也就是说，第 $i$ 个病毒最后都会分裂成一个危害值为 $\\{1,2,3,\\ldots,b_i\\}$ 的病毒序列，当所有病...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments