CF1743F Intersection and Union

给定 $n$ 个坐标轴上的线段，第 $i$ 个线段为 $[l_i, r_i]$。我们用 $S_i$ 表示第 $i$ 个线段上所有属于该线段的整数点的集合。 记 $A \cup B$ 表示集合 $A$ 和 $B$ 的并集，$A \cap B$ 表示集合 $A$ 和 $B$ 的交集，$A \oplus B$ 表示集合 $A$ 和 $B$ 的对称差集（即包含所有属于 $A$ 或 $B$ 但不同时属于 $A$ 和 $B$ 的元素的集合）。 设 $[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$ 是一个长度为 $n-1$ 的数组，每个元素可以是 $\cup$、$\oplus$ 或 $\cap$。对于所有 $3^{n-1}$ 种选择该数组的方式，计算以下表达式的值之和： $$ |(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n| $$ 其中 $|S|$ 表示集合 $S$ 的大小。

第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^5$）。 接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i \le r_i \le 3 \cdot 10^5$）。

输出一个整数，表示所有可能的 $[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$ 选择下 $|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$ 的和。由于答案可能很大，请输出对 $998244353$ 取模后的结果。

由 ChatGPT 4.1 翻译