CF1774G Segment Covering

ChthollyNotaSeniorious 给了 DataStructures 一条数轴，上面有 $m$ 个互不相同的线段。设 $f(l,r)$ 表示选择偶数个线段，使得它们的并恰好为 $[l,r]$ 的方案数，$g(l,r)$ 表示选择奇数个线段，使得它们的并恰好为 $[l,r]$ 的方案数。 ChthollyNotaSeniorious 向 DataStructures 提出了 $q$ 个问题。在每个询问中，ChthollyNotaSeniorious 会给出两个数 $l, r$，现在他希望你能帮他计算 $f(l,r)-g(l,r)$ 模 $998\,244\,353$ 的值，这样他就不会让她失望了。

输入的第一行包含两个整数 $m$（$1 \leq m \leq 2 \cdot 10^5$）和 $q$（$1 \leq q \leq 2 \cdot 10^5$），分别表示线段的数量和询问的数量。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i < y_i \leq 10^9$），表示一条线段 $[x_i, y_i]$。 保证所有线段互不相同。更正式地说，不存在 $1 \leq i < j \leq m$ 使得 $x_i = x_j$ 且 $y_i = y_j$。 接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i < r_i \leq 10^9$），描述一次询问。

对于每个询问，输出一个整数，表示 $f(l_i,r_i)-g(l_i,r_i)$ 模 $998\,244\,353$ 的结果。

在第一个询问中，我们需要计算 $f(1, 4) - g(1, 4)$。唯一一个线段子集的并为 $[1, 4]$，即 $\{[1, 3], [2, 4]\}$，所以 $f(1, 4) = 1, g(1, 4) = 0$。 在第二个询问中，我们需要计算 $f(1, 5) - g(1, 5)$。唯一的线段子集的并为 $[1, 5]$ 的有 $\{[1, 3], [2, 4], [3, 5]\}$ 和 $\{[1, 3], [3, 5]\}$，所以 $f(1, 5) = 1, g(1, 5) = 1$。 由 ChatGPT 4.1 翻译