AT_npcapc_2024_g Many Common Segment Problems

PCT 君出了一道如下的题目。 > **Common Segment** > > 给定 $N$ 个区间 $[L_1, R_1], [L_2, R_2], \dots, [L_N, R_N]$，其中 $[L, R]$ 表示所有满足 $L \leq x \leq R$ 的整数 $x$ 构成的区间。 > > 从这 $N$ 个区间中选出至少一个区间的方法有 $2^N-1$ 种，其中选出的所有区间的公共部分非空的方案数，模 $998244353$ 输出。 但 PCT 君不小心丢失了一部分区间的 $L_i, R_i$ 的值，这令他很困扰。请你帮他解决以下问题。 > **Many Common Segment Testcases** > > 给定 **Common Segment** 的一个测试用例，其中部分丢失的 $L_i, R_i$ 的值用 $-1$ 替代。 > > 其中，原本的测试用例满足 $1 \leq L_i \leq R_i \leq M\ (1 \leq i \leq N)$。 > > 对所有可能的原本测试用例，分别求出对应的 **Common Segment** 答案，最后将所有答案的总和模 $998244353$ 输出。

输入从标准输入读取，格式如下： > $N$ $M$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$

输出答案。

### 部分分 本题包含多个部分分。 - 若你能解决 $L_i,R_i \geq 1$ 的数据集，将获得 $10$ 分。 - 若你能解决 $N, M \leq 2000$ 的数据集，将获得 $10$ 分。 ### 样例解释 1 全部可能的测试用例及其对应的 **Common Segment** 答案如下所示。 - $(L_i, R_i) = (1,1), (2,2), (2,3)$ 时，答案为 $4$ - $(L_i, R_i) = (1,2), (2,2), (2,3)$ 时，答案为 $7$ - $(L_i, R_i) = (1,3), (2,2), (2,3)$ 时，答案为 $7$ 因此，最终答案为 $4 + 7 + 7 = 18$。 ### 数据范围 - $1 \leq N, M \leq 10^5$ - $L_i = -1$ 或 $1 \leq L_i \leq M$ - $R_i = -1$ 或 $1 \leq R_i \leq M$ - 若 $L_i, R_i \geq 1$，则有 $L_i \leq R_i$。 由 ChatGPT 5 翻译