「DTOI-2」星之界

Luogu

IDLGP8576

Time1500ms

Memory511MB

DifficultyP6

O2优化分块

夜空中的星星组成了一个序列 $a$，序列中的第 $i$ 个数表示第 $i$ 颗星星的亮度。现在，作为星之眷顾者的你，拥有两种方式来操作星星。 - 操作一：输入格式为 $\texttt{1 l r x y}$，表示将 $[l,r]$ 内所有亮为 $x$ 的星星的亮度改为 $y$。 - 操作二：输入格式为 $\texttt{2 l r}$，表示输出 $ \prod\limits_{i = l}^{r} C_{\sum_{j = l}^{i}a_j}^{a_i}\ \bmod 998244353 $ 的值。 ## Input 输入第一行，两个整数 $n,q$，表示序列长度与操作次数。第二行，$n$ 个整数，表示初始序列值。接下来 $q$ 行，每行一个操作，格式由上方给出。 ## Output 对于每个 $2$ 操作，输出所求值。 [samples] ## Background >天仙开碧落，银界失黄昏。 ## Note **样例解释#1** 直接按照题意计算可得。 | $\textbf{Subtask}$ | $n \le$ | $q \le$ | 特殊性质 | 总分数 | | :----------: | :---------------: | :---------------: | :-------------: | :---: | | $1$ | $10$ | $15$ | 无 | $5$ | | $2$ | $10^3$ | $10^3$ | 无 | $10$ | | $3$ | $5\times 10^4$ | $5\times 10^4$ | 只有操作 $2$ | $10$ | | $4$ | $5\times 10^4$ | $5\times 10^4$ | 只有一次操作 $2$ | $10$ | | $5$ | $5\times 10^4$ | $5\times 10^4$ | 无 | $21$ | | $6$ | $10^5$ | $10^5$ | $\sum a[i] \le 5\times 10^5$ | $14$ | | $7$ | $10^5$ | $10^5$ | 无 | $30$ | 对于 $100\%$ 的数据，$1 \le n,q,a_i \le 10^5$。有 $1 \le l,r\le n;1 \le x,y\le 10^5$。任意时刻 $\sum a$ 不会超过 $10^7$。

Samples

Input #1

Output #1

2520
35

Input #2

Output #2

412013881
4084080
210

API Response (JSON)

{
  "problem": {
    "name": "「DTOI-2」星之界",
    "description": {
      "content": "夜空中的星星组成了一个序列 $a$，序列中的第 $i$ 个数表示第 $i$ 颗星星的亮度。 现在，作为星之眷顾者的你，拥有两种方式来操作星星。 - 操作一：输入格式为 $\\texttt{1 l r x y}$，表示将 $[l,r]$ 内所有亮为 $x$ 的星星的亮度改为 $y$。   - 操作二：输入格式为 $\\texttt{2 l r}$，表示输出 $ \\prod\\limits_{i = l",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 523264
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8576"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "夜空中的星星组成了一个序列 $a$，序列中的第 $i$ 个数表示第 $i$ 颗星星的亮度。\n\n现在，作为星之眷顾者的你，拥有两种方式来操作星星。\n\n- 操作一：输入格式为 $\\texttt{1 l r x y}$，表示将 $[l,r]$ 内所有亮为 $x$ 的星星的亮度改为 $y$。\n \n- 操作二：输入格式为 $\\texttt{2 l r}$，表示输出 $ \\prod\\limits_{i = l...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments