Intersection and Union
Contest: Educational Codeforces Round 137 (Rated for Div. 2)
Difficulty rating: 2300
Tags: data structures, dp, matrices, probabilities

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$$$.

Input format:
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 format:
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$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
4
3 5
4 8
2 2
1 9

Example output:
162

Example input:
4
1 9
3 5
4 8
2 2

Example output:
102

Editorial:
We will use the Contribution to the Sum technique to solve this problem: for every integer from $$$0$$$ to $$$300000$$$, let's calculate the number of ways to choose the operators so it belongs to the result, and add all of the results.
For a fixed integer $$$x$$$, the number of ways to choose the operators so that $$$x$$$ belongs to the result can be done as follows: let $$$dp_{i,f}$$$ be the number of ways to choose the first $$$i$$$ operators so that, after applying them, the resulting set contains $$$x$$$ if $$$f = 1$$$, and does not contain $$$x$$$ if $$$f = 0$$$. The transitions from $$$dp_i$$$ to $$$dp_{i+1}$$$ depend on whether the number $$$x$$$ belongs to the segment $$$i+1$$$.
Obviously, this is too slow if we compute the dynamic programming from scratch for every integer $$$x$$$. Instead, we can notice that the transitions from $$$dp_i$$$ to $$$dp_{i+1}$$$ are linear combinations: both $$$dp_{i+1,0}$$$ and $$$dp_{i+1,1}$$$ are linear combinations of $$$dp_{i,0}$$$ and $$$dp_{i,1}$$$ with coefficients depending on whether the element $$$x$$$ belongs to the set or not. So, transitioning from $$$dp_i$$$ to $$$dp_{i+1}$$$ can be written in terms of multiplying by a $$$2 \times 2$$$ matrix.
Let's build a segment tree where each vertex stores a transition matrix, and operations are "calculate the product of matrices on a segment" and "replace a matrix at some index". We can build a sequence of these transition matrices for $$$x=0$$$ and store them in the segment tree; for $$$x=1$$$, this sequence of transition matrices will change only in positions $$$j$$$ such that either $$$0$$$ belongs to $$$[l_j, r_j]$$$ and $$$1$$$ does not belong to it, or vice versa. So, we can go from $$$x=0$$$ to $$$x=1$$$ by replacing these transition matrices in the segment tree. For $$$x=2$$$, the only changes from $$$x=0$$$ are in positions $$$j$$$ such that either $$$1$$$ belongs to $$$[l_j, r_j]$$$ and $$$2$$$ does not belong to it, or vice versa — and we can replace the matrices in these positions as well. In total, there will be only $$$O(n)$$$ such replacements; so, we solve the problem in $$$O(M + n \log M)$$$, where $$$M$$$ is the constraint on the numbers belonging to the sets.