Intersection and Union
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given $n$ segments on the coordinate axis. The $i$-th segment is $[l_i, r_i]$. Let's denote the set of all integer points belonging to the $i$-th segment as $S_i$.
Let $A \cup B$ be the union of two sets $A$ and $B$, $A \cap B$ be the intersection of two sets $A$ and $B$, and $A \oplus B$ be the symmetric difference of $A$ and $B$ (a set which contains all elements of $A$ and all elements of $B$, except for the ones that belong to both sets).
Let $[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$ be an array where each element is either $\cup$, $\oplus$, or $\cap$. Over all $3^{n-1}$ ways to choose this array, calculate the sum of the following values:
$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$
In this expression, $|S|$ denotes the size of the set $S$.
The first line contains one integer $n$ ($2 \le n \le 3 \cdot 10^5$).
Then, $n$ lines follow. The $i$-th of them contains two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 3 \cdot 10^5$).
Print one integer — the sum of $|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$ over all possible ways to choose $[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$. Since the answer can be huge, print it modulo $998244353$.
Input
The first line contains one integer $n$ ($2 \le n \le 3 \cdot 10^5$).
Then, $n$ lines follow. The $i$-th of them contains two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 3 \cdot 10^5$).
Output
Print one integer — the sum of $|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$ over all possible ways to choose $[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$. Since the answer can be huge, print it modulo $998244353$.
4
3 5
4 8
2 2
1 9
4
1 9
3 5
4 8
2 2
162
102
20240118期望的线性选讲
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 12
- Start at
- 2024-1-18 8:00
- End at
- 2024-1-23 8:00
- Duration
- 120 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 19