CF981G Magic multisets

在 Dirtpolis 的魔法学校里，计算机科学课上研究了许多有趣的对象。 例如，考虑一种“魔法多重集”。如果你尝试向多重集中添加一个已经存在的整数，则多重集中的每个元素都会复制一份。例如，如果你尝试向多重集 $\{1, 2, 3, 3\}$ 添加整数 $2$，你将得到 $\{1, 1, 2, 2, 3, 3, 3, 3\}$。 如果你尝试添加一个多重集中不存在的整数，则它会被直接加入多重集。例如，如果你尝试向多重集 $\{1, 2, 3, 3\}$ 添加整数 $4$，你将得到 $\{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 \times 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, 2\}, \{1, 2\}, \{\}, \{\}]$，第三次操作后变为 $[\{1, 1, 2, 2\}, \{1, 1, 2, 2\}, \{1\}, \{1\}]$。 在第二个样例中，第一个多重集的变化过程如下： $\{\} \to \{3\} \to \{3, 3\} \to \{2, 3, 3\} \to \{1, 2, 3, 3\} \to \{1, 1, 2, 2, 3, 3, 3, 3\}$。 由 ChatGPT 4.1 翻译