CF981E Addition on Segments

Grisha 参加了一场比赛，遇到了如下问题。 给定一个长度为 $n$ 的数组，初始时数组中的所有元素均为 $0$。数组的下标从 $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$ 到 $r_i$ 的所有元素上。所有操作完成后，你需要求出数组中的最大值。 Grisha 很聪明，很快就解决了这个问题。 但他突然想到另一个问题：“如果我们对数组应用某个操作的子集（可以为空），数组中的最大值可能是多少？” 请你帮助 Grisha，找出所有 $1$ 到 $n$ 之间的整数 $y$，使得存在某个操作的子集（可以为空），使得数组中的最大值恰好等于 $y$。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^{4}$），分别表示数组的长度和操作的数量。 接下来的 $q$ 行，每行包含三个整数 $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$ 之间，能够作为数组最大值的整数的个数。 第二行输出这 $k$ 个整数，按升序排列，表示所有可能作为最大值的整数。

考虑第一个样例。如果只选择第一个操作，最大值为 $1$。如果只选择第二个操作，最大值为 $2$。如果选择前两个操作，最大值为 $3$。如果只选择第四个操作，最大值为 $4$。如果选择第四个操作和其他操作，最大值会超过 $n$，因此不应输出。 在第二个样例中，可以通过选择第一个操作得到最大值 $1$，选择第二个操作得到最大值 $2$，选择所有操作得到最大值 $3$。 在第三个样例中，可以得到如下最大值： - 只用操作 $(1)$，最大值为 $2$。 - 只用操作 $(2)$，最大值为 $3$。 - 用操作 $(1, 2)$，最大值为 $5$。 - 只用操作 $(3)$，最大值为 $6$。 - 用操作 $(1, 3)$，最大值为 $8$。 - 用操作 $(2, 3)$，最大值为 $9$。 由 ChatGPT 4.1 翻译