← 返回题目列表

AtCoder · npcapc_2024_g

G. 许多常见的段问题

中文机器翻译题面 查看原题

配点 : 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