[Solution] Intersection and Union Codeforces Solution

F. Intersection and Union

time limit per test

5 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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 [𝑜𝑝1,𝑜𝑝2,…,𝑜𝑝𝑛−1]$[{op}_1,{op}_2,\dots ,{op}_{n-1}]$ be an array where each element is either ∪$\cup$, ⊕$\oplus$, or ∩$\cap$. Over all 3𝑛−1$3^{n-1}$ ways to choose this array, calculate the sum of the following values:

|(((𝑆1 𝑜𝑝1 𝑆2) 𝑜𝑝2 𝑆3) 𝑜𝑝3 𝑆4) … 𝑜𝑝𝑛−1 𝑆𝑛|$$|(((S_1{op}_1{S}_2){op}_2{S}_3){op}_3{S}_4)\dots {op}_{n-1}{S}_n|$$

In this expression, |𝑆|$|S|$ denotes the size of the set 𝑆$S$.

Input

The first line contains one integer 𝑛$n$ (2≤𝑛≤3⋅105$2\le n\le 3\cdot {10}^5$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Then, 𝑛$n$ lines follow. The 𝑖$i$-th of them contains two integers 𝑙𝑖$l_i$ and 𝑟𝑖$r_i$ (0≤𝑙𝑖≤𝑟𝑖≤3⋅105$0\le l_i\le r_i\le 3\cdot {10}^5$).

Output

Print one integer — the sum of |(((𝑆1 𝑜𝑝1 𝑆2) 𝑜𝑝2 𝑆3) 𝑜𝑝3 𝑆4) … 𝑜𝑝𝑛−1 𝑆𝑛|$|(((S_1{op}_1{S}_2){op}_2{S}_3){op}_3{S}_4)\dots {op}_{n-1}{S}_n|$ over all possible ways to choose [𝑜𝑝1,𝑜𝑝2,…,𝑜𝑝𝑛−1]$[{op}_1,{op}_2,\dots ,{op}_{n-1}]$. Since the answer can be huge, print it modulo 998244353$998244353$.