配点 : 100 点
問題文
PCT 您造成了以下问题。
公共段
N 间隔 给出了 [L_1,R_1],[L_2,R_2],\dots,[L_N,R_N] 。这里 [L, R] 是 您也可以写 L 以上 R 表示由以下所有整数组成的区间。
从这里 如何选择超过 1 的间隔是 2^N-1 有多种方法,但让我们计算所有选定区间的公共部分不为空的情况的数量。 除以 998244353 后求余数。
PCT 您在编写测试用例时犯了一个错误。 我丢失了 L_i,R_i 中的一些值。请为遇到困难的他解决以下问题。
许多常见的段测试用例 我们得到了一个测试用例
公共段 。然而我却把它弄丢了 L_i,R_i 的值是
-1。 对于此时原来的测试用例是 1 \le L_i \le R_i \le M\ (1 \le i \le N) 很满意。对于所有可能的原始测试用例 求解 公共段 并求答案之和。 998244353 后求余数。
制約
- 1 \le N,M \le 10^5
- L_i = -1 或 至少 1 \le L_i \le M
- R_i = -1 或 至少 1 \le R_i \le M
- L_i,R_i \ge 1 如果 L_i \le R_i
部分点
这个问题有多个部分点。 如果正确答案是满足
- L_i,R_i \ge 1 的数据集 10 点。 如果您正确回答了所有满足
- N,M \le 2000 的数据集 10 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N M L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
打印答案。 来自
入力例 1
3 3 1 -1 2 2 2 3
出力例 1
18
所有可能的测试用例及其对应的测试用例 公共段 的答案如下。
- (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 。 对于
入力例 2
5 8 1 7 2 3 4 8 6 8 1 5
出力例 2
15
入力例 3
10 13 4 -1 -1 -1 7 11 -1 -1 -1 -1 -1 -1 11 -1 3 8 -1 9 -1 -1
出力例 3
841024210