← 返回题目列表

Codeforces · 981/E

E. 段上的添加

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

Grisha 参加比赛并遇到以下问题。

给定一个大小为 $$$n$$$ 的数组,最初由零组成。数组的元素从 $$$1$$$ 到 $$$n$$$ 进行枚举。您对数组执行 $$$q$$$ 操作。第 $$$i$$$ 操作由三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$x_i$$$ 描述($$$1 \leq l_i \leq r_i \leq n$$$、$$$1 \leq x_i \leq n$$$),这意味着您应该将 $$$x_i$$$ 添加到每个带有索引的元素$$$l_i,l_i + 1,\ldots,r_i$$$。完成所有操作后,您应该找到数组中的最大值。

Grisha很聪明,所以他很快就解决了问题。

然而,他的脑子里出了问题,现在他想到了以下问题:“考虑我们对数组应用了一些操作子集。数组中最大值的可能值是多少?”

帮助 Grisha,找到 $$$1$$$ 和 $$$n$$$ 之间的所有整数 $$$y$$$,这样,如果您应用操作的某个子集(可能为空),则数组中的最大值将等于 $$$y$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 10^{4}$$$) - 数组的长度和初始问题中的查询数量。

以下 $$$q$$$ 行包含查询,每行一个。这些行的第 $$$i$$$ 包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$x_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$1 \leq x_i \leq n$$$),表示将 $$$x_i$$$ 添加到段的查询数组的第 $$$l_i$$$ 到第 $$$r_i$$$ 个元素(包含在内)。

输出

在第一行中打印唯一的整数 $$$k$$$,表示从 $$$1$$$ 到 $$$n$$$(含)的整数个数,在应用给定操作的某些子集(可能为空)后,该整数可以等于数组中的最大值。

在下一行中打印从 $$$1$$$ 到 $$$n$$$ 的这些 $$$k$$$ 整数 - 最大值的可能值。按升序打印这些整数。

示例

输入 #1

4 3
1 3 1
2 4 2
3 4 4

输出 #1

4
1 2 3 4

输入 #2

7 2
1 5 1
3 7 2

输出 #2

3
1 2 3

输入 #3

10 3
1 1 2
1 1 3
1 1 6

输出 #3

6
2 3 5 6 8 9

注意

考虑第一个例子。如果仅考虑第一个查询的子集,则最大值等于 $$$1$$$。如果仅进行第二个查询,则最大值等于 $$$2$$$。如果您执行前两个查询,则最大值将变为 $$$3$$$。如果仅进行第四个查询,则最大值变为 $$$4$$$。如果您执行第四个查询以及更多查询,则最大值将大于 $$$n$$$,因此您不应打印它。

在第二个示例中,您可以使用第一个查询来获取 $$$1$$$。您可以仅使用第二个查询来获取$$$2$$$。您可以进行所有查询以获得$$$3$$$。

在第三个示例中,您可以获得以下最大值:

- 您可以通过使用查询来实现 $$$2$$$ 的最大值:$$$(1)$$$。
- 您可以通过使用查询来实现 $$$3$$$ 的最大值:$$$(2)$$$。
- 您可以通过使用查询来实现 $$$5$$$ 的最大值:$$$(1, 2)$$$。
- 您可以通过使用查询来实现 $$$6$$$ 的最大值:$$$(3)$$$。
- 您可以通过使用查询来实现 $$$8$$$ 的最大值:$$$(1, 3)$$$。
- 您可以通过使用查询来实现 $$$9$$$ 的最大值:$$$(2, 3)$$$。