← 返回题目列表

Codeforces · 1743/F

F. 交集和并集

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

坐标轴上有 $$$n$$$ 段。第$$$i$$$段是$$$[l_i, r_i]$$$。我们将属于第$$$i$$$段的所有整数点的集合表示为$$$S_i$$$。

设 $$$A \cup B$$$ 为两个集合 $$$A$$$ 和 $$$B$$$ 的并集,$$$A \cap B$$$ 为两个集合 $$$A$$$ 和 $$$B$$$ 的交集,$$$A \oplus B$$$ 为 $$$A$$$ 和 $$$B$$$ 的对称差(包含所有元素的集合) $$$A$$$ 的元素和 $$$B$$$ 的所有元素(属于两个集合的元素除外)。

设 $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{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$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3 \cdot 10^5$$$)。

输出

打印一个整数 — $$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$ 在所有可能的选择方式上的总和$$$[\mathbin{op}_1、\mathbin{op}_2、\dots、\mathbin{op}_{n-1}]$$$。由于答案可能很大,请打印它对 $$$998244353$$$ 取模。

示例

输入 #1

4
3 5
4 8
2 2
1 9

输出 #1

162

输入 #2

4
1 9
3 5
4 8
2 2

输出 #2

102