Intersection and Union (Codeforces 1743F)
Tags: DP, matrices

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


Sample Inputs:
4
3 5
4 8
2 2
1 9

4
1 9
3 5
4 8
2 2

Sample Outputs:
162

102

Solution (Python):
import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = 998244353
pow2 = [1]
for _ in range(300001):
    pow2.append(pow2[-1] * 2 % M)
pow3 = [1]
for _ in range(300001):
    pow3.append(pow3[-1] * 3 % M)

def main(t):
    n = int(input())
    segs = []
    m = 0
    accu = 0
    for _ in range(n):
        (l, r) = map(int, input().split())
        segs.append([l, r])
        accu += r - l + 1
        m = max(m, r)
    lastappear = [-1] * (m + 1)
    rest = [i for i in range(m + 1)]
    for i in range(n - 1, -1, -1):
        [l, r] = segs[i]
        locl = bisect.bisect_left(rest, l)
        locr = bisect.bisect(rest, r)
        for j in range(locl, locr):
            if lastappear[rest[j]] < 0:
                lastappear[rest[j]] = i
        if locr - locl > 30:
            rest[locl:locr] = []
    ans = 0
    for j in range(m + 1):
        if lastappear[j] < 0:
            continue
        if lastappear[j] == 0:
            base = 1
        else:
            base = 2 * pow3[lastappear[j] - 1]
        base = base * pow2[n - 1 - lastappear[j]] % M
        ans = (ans + base) % M
    print(ans)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = 998244353
pow2 = [1]
for _ in range(300001):
    pow2.append(pow2[-1] * 2 % M)
pow3 = [1]
for _ in range(300001):
    pow3.append(pow3[-1] * 3 % M)

def main(t):
    n = int(input())
    segs = []
    m = 0
    accu = 0
    for _ in range(n):
        (l, r) = map(int, input().split())
        segs.append([l, r])
        accu += r - l + 1
        m = max(m, r)
    lastappear = [-1] * (m + 1)
    rest = [i for i in range(m + 1)]
    if accu > 30 * n:
        for i in range(n - 1, -1, -1):
            [l, r] = segs[i]
            locl = bisect.bisect_left(rest, l)
            locr = bisect.bisect(rest, r)
            for j in range(locl, locr):
                lastappear[rest[j]] = i
            rest[locl:locr] = []
    else:
        for i in range(n - 1, -1, -1):
            [l, r] = segs[i]
            for j in range(l, r + 1):
                if lastappear[j] < 0:
                    lastappear[j] = i
    ans = 0
    for j in range(m + 1):
        if lastappear[j] < 0:
            continue
        if lastappear[j] == 0:
            base = 1
        else:
            base = 2 * pow3[lastappear[j] - 1]
        base = base * pow2[n - 1 - lastappear[j]] % M
        ans = (ans + base) % M
    print(ans)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = 998244353
pow2 = [1]
for _ in range(300001):
    pow2.append(pow2[-1] * 2 % M)
pow3 = [1]
for _ in range(300001):
    pow3.append(pow3[-1] * 3 % M)

def main(t):
    n = int(input())
    segs = []
    m = 0
    accu = 0
    for _ in range(n):
        (l, r) = map(int, input().split())
        segs.append([l, r])
        accu += r - l + 1
        m = max(m, r)
    lastappear = [-1] * (m + 1)
    rest = [i for i in range(m + 1)]
    for i in range(n - 1, -1, -1):
        [l, r] = segs[i]
        locl = bisect.bisect_left(rest, l)
        locr = bisect.bisect(rest, r)
        for j in range(locl, locr):
            if lastappear[rest[j]] < 0:
                lastappear[rest[j]] = i
        if locr - locl > 30:
            rest[locl:locr] = []
    ans = 0
    for j in range(m + 1):
        if lastappear[j] < 0:
            continue
        if lastappear[j] == 0:
            base = 1
        else:
            base = 2 * pow3[lastappear[j] - 1]
        base = base * pow2[n - 1 - lastappear[j]] % M
        ans = (ans + base) % M
    print(ans)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1