← 返回题目列表

Codeforces · 981/G

G. 魔法多组

中文机器翻译题面 查看原题

在 Dirtpolis 的魔法学校,计算机科学课上研究了很多有趣的物体。

例如,考虑神奇的多重集。如果您尝试向其中添加多重集中已存在的整数,则多重集中的每个元素都会重复。例如,如果您尝试将整数 $$$2$$$ 添加到多重集 $$$\{1, 2, 3, 3\}$$$,您将得到 $$$\{1, 1, 2, 2, 3, 3, 3, 3\}$$$。

如果您尝试添加多重集中未出现的整数,则只需将其添加到其中即可。例如,如果您尝试将整数 $$$4$$$ 添加到多重集 $$$\{1, 2, 3, 3\}$$$,您将得到 $$$\{1, 2, 3, 3, 4\}$$$。

还要考虑 $$$n$$$ 最初为空的魔法多重集的数组,从 $$$1$$$ 到 $$$n$$$ 枚举。

你要回答 $$$q$$$ 形式的查询“将整数 $$$x$$$ 添加到所有索引为 $$$l, l + 1, \ldots, r$$$ 的多重集”和“计算索引为 $$$l, l + 1, \ldots, r$$$ 的多重集的大小总和”。第二种类型查询的答案可能很大,因此打印答案对 $$$998244353$$$ 取模。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^{5}$$$) - 分别是数组中魔法多重集的数量和查询的数量。

接下来的 $$$q$$$ 行描述查询,每行一个。每行都以整数 $$$t$$$ ($$$1 \leq t \leq 2$$$) 开头——查询的类型。如果 $$$t$$$ 等于 $$$1$$$,则后面跟着三个整数 $$$l$$$、$$$r$$$、$$$x$$$ ($$$1 \leq l \leq r \leq n$$$、$$$1 \leq x \leq n$$$),这意味着您应该将 $$$x$$$ 添加到索引从 $$$l$$$ 到$$$r$$$ 包括在内。如果 $$$t$$$ 等于 $$$2$$$,则后面跟着两个整数 $$$l$$$、$$$r$$$ ($$$1 \leq l \leq r \leq n$$$),这意味着您应该计算索引从 $$$l$$$ 到 $$$r$$$ 的所有多重集的大小总和。

输出

对于第二种类型的每个查询,打印给定段上多重集的大小总和。

答案可能很大,因此请以 $$$998244353$$$ 为模打印它们。

示例

输入 #1

4 4
1 1 2 1
1 1 2 2
1 1 4 1
2 1 4

输出 #1

10

输入 #2

3 7
1 1 1 3
1 1 1 3
1 1 1 2
1 1 1 1
2 1 1
1 1 1 2
2 1 1

输出 #2

4
8

注意

在前两个查询之后的第一个示例中,多重集等于 $$$[\{1, 2\},\{1, 2\},\{\},\{\}]$$$,在第三个查询之后,它们等于 $$$[\{1, 1, 2, 2\},\{1, 1, 2, 2\}、\{1\}、\{1\}]$$$。

在第二个示例中,第一个多重集演变如下:

$$$\{\} \到 \{3\} \到 \{3, 3\} \到 \{2, 3, 3\} \到 \{1, 2, 3, 3\} \到 \{1, 1, 2, 2, 3, 3, 3, 3\}$$$。