3758: 我是 D 题(第六轮04)
题目描述
若有一个长度为 n 的数列 {an } 满足 ∀ai ∈ [1, m]，定义 f({an }) 为数列中所有 极长相等子段长度的平方和。
现在给出长度为 n 的数列 {bn }，满足 ∀bi ∈ [0, m]， bi = 0 表示 bi 的取值在 [1, m]中均匀随机。
有 q 次操作，每次修改数列 {bn } 中的一个值，或者询问 f({bl ~r }) 的值对 998244353 取模后的结果。
输入
第一行三个正整数 n, m, q 。
第二行 n 个正整数表示序列 {bn } 。 接下来 q 行，每行第一个数为 opt。
- 若 opt = 1，则接下来给出两个整数 p, x，表示将 bp 修改为 x 。
- 若 opt = 2 ，则 接下来给 出两个整 数 l, r ，表 示询问 f({bl ~r }) 的值 对 998244353 取模后的结果。
输出
请你对每个 opt = 2 的操作给出对应的答案。
样例输入 复制
10 10 3
1 2 5 3 0 0 2 2 0 1
2 2 9
1 5 4
2 1 10样例输出 复制
205638348
259543545提示
【数据范围】
对于前 10% 的数据，保证 n, m ≤ 7, q ≤ 5000。
对于接下来 15% 的数据，保证 n, m, q ≤ 600 。
对于接下来 15% 的数据，保证 m = 2。
对于接下来 10% 的数据，保证 q = 1, ∀i, bi = 0。
对于接下来 10% 的数据， q = 1。
对于接下来 20% 的数据， l = 1, r = n。
对于 100% 的 数据，保 证 n, q ≤ 5 × 1^05 ,1 ≤ m ≤ 998244352,1 ≤ p, l, r ≤ n, 0 ≤ x ≤ 998244352。