Good Subsets
Contest: Kotlin Heroes: Episode 1
Tags: *special, dp

You are given $$$n$$$ segments on the $$$Ox$$$ axis. The $$$i$$$-th segment is given as a pair $$$l_i, r_i$$$, where $$$l_i$$$ is the position of the left end of the $$$i$$$-th segment and $$$r_i$$$ is the position of the right end of the $$$i$$$-th segment. Segments may intersect, overlap, or even coincide. A segment is a set of numbers (including floating-point numbers) lying between the segment ends or coinciding with them. Formally, the segment $$$[l, r]=\{x~|~x \in \Bbb{R},~l \le x \le r\}$$$.

Let the union of segments be the set of all axis points covered by the set of segments. Let's call a subset of the given segments good if its union equals the union of all $$$n$$$ segments.

Your task is to calculate the number of good subsets of the given $$$n$$$ segments. Since the answer may be very large, print it modulo $$$998244353$$$.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of segments.

The next $$$n$$$ lines contain segments. The $$$i$$$-th segment is given as a pair $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$), where $$$l_i$$$ is the left border of the segment and $$$r_i$$$ is the right border of the segment. Segments may intersect, overlap, or even coincide.

Output format:
Print the number of good subsets of the given set of segments. Since the answer may be very large, print it modulo $$$998244353$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Example input:
3
1 1
2 6
1 6

Example output:
4

Example input:
2
3 4
2 5

Example output:
2

Editorial:
Let's consider components of connected segments separately and solve the problem for each of these components. The answer will be product of answers over all components. How to calculate the answer for some component?
Let $$$[lf; rg]$$$ be the whole segment covered by the component. Let's do the following dynamic programming: $$$dp_{pos}$$$ is the number of ways to choose the subset of segments to cover all points in segment $$$[lf; pos]$$$. The base of this dynamic programming is $$$dp_{lf - 1} = 1$$$, other values of $$$dp$$$ are zeros. Let's choose the order in which we will consider segments. It is very intuitively that we need to consider all segments in order of non-decreasing of their left border (because we calculate the dynamic programming from left to right).
What should we do with the current segment ($$$l_i, r_i$$$)? Let's understand how it can affect the final answer. There are two cases: it can extend the covered segment or not extend it.
If it extends the segment then we can do the following transition: $$$dp_{r_i} = dp_{r_i} + \sum\limits_{j=l_i-1}^{r_i - 1} dp_j$$$. What it means? It means that the union of the considered subsets of segments should ends in at least in $$$l_i - 1$$$ (otherwise the segment $$$[lf; rg]$$$ will not be fully covered), but not righter than $$$r_i - 1$$$ (otherwise the segment ($$$l_i, r_i$$$) will not extend the covered segment). So all subsets of segments that ends in $$$[l_i - 1; r_i - 1]$$$ are suitable for this case.
The other case is when the current segment does not extend the covered segment. In this case we can multiply by two all values of $$$dp$$$ from $$$r_i$$$ to $$$rg$$$ inclusive (set $$$dp_j := 2 dp_j$$$ for each $$$j \in [r_i; rg]$$$). Note that you should firstly multiply the value of $$$dp_{r_i}$$$ by two and then do the first transition.
The answer for the component is $$$dp_{rg}$$$. Don't forget about the modulo!
The first thing is that this solution is bugged. It considers only integer points of union, but we need to consider all points of union. How can we avoid it? Just multiply all coordinates by two!
And notes about implementation: the first note is that the solution above is quadratic. Why is it quadratic? Because we don't need any points except $$$l_i - 1, l_i, l_i + 1$$$ and $$$r_i - 1, r_i, r_i + 1$$$ for each segment. So there are $$$O(n)$$$ points we consider and each transition can be done in $$$O(n)$$$. But this solution can be improved to $$$O(n \log n)$$$ using the very standard segment tree with lazy propagation. All operations we need is to multiplying by two on segment, getting the sum on segment and addition in point. And the second note is: if you don't want to write implicit segment tree, don't forget to compress coordinates.