CF1557D Ezzat and Grid
题目描述
Moamen 正在绘制一个包含 $n$ 行 $10^9$ 列、仅由数字 $0$ 和 $1$ 组成的网格。Ezzat 注意到 Moamen 的绘图，并对最少需要删除多少行才能使网格变得“美丽”产生了兴趣。
如果对于任意两行相邻的行，存在至少一列在这两行中都包含 $1$，则称该网格是美丽的。
Ezzat 会给你行数 $n$ 和 $m$ 个包含 $1$ 的网格区间。每个区间由三个整数 $i$、$l$ 和 $r$ 表示，其中 $i$ 表示行号，$l$ 和 $r$ 表示该行中从第 $l$ 列到第 $r$ 列（包含两端）都为 $1$。
例如，若 $n=3$，$m=6$，区间为 $(1,1,1)$、$(1,7,8)$、$(2,7,7)$、$(2,15,15)$、$(3,1,1)$、$(3,15,15)$，则网格如下所示：
你的任务是告诉 Ezzat，最少需要删除多少行才能使网格变得美丽。
输入格式
第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 3 \cdot 10^5$）。
接下来的 $m$ 行，每行包含三个整数 $i$、$l$ 和 $r$（$1 \le i \le n$，$1 \le l \le r \le 10^9$）。每一行表示第 $i$ 行的第 $l$ 列到第 $r$ 列（包含两端）都为 $1$。
注意，这些区间可能会重叠。
输出格式
第一行输出一个整数 $k$，表示最少需要删除的行数。
第二行输出 $k$ 个不同的整数 $r_1, r_2, \ldots, r_k$，表示需要删除的行号（$1 \le r_i \le n$），顺序任意。
如果有多组答案，输出任意一组均可。
说明/提示
在第一个测试样例中，网格如题目描述所示。该网格具有以下性质：
1. 第 $1$ 行和第 $2$ 行在第 $7$ 列有公共的 $1$。
2. 第 $2$ 行和第 $3$ 行在第 $15$ 列有公共的 $1$。
因此，该网格是美丽的，不需要删除任何行。
在第二个测试样例中，给定的网格如下：
由 ChatGPT 4.1 翻译