CF796F Sequence Recovery

Zane 曾经拥有一个好的数列 $a$，它由 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$ 组成 —— 但他现在已经弄丢了它。 如果一个数列的所有整数都是非负且不超过 $10^{9}$，则称其为“好”的数列。 然而，Zane 还记得他曾经对这个数列进行了 $m$ 次操作。 操作分为两种类型： 1. 给定 $l$ 和 $r$，查询下标 $i$ 满足 $l \leq i \leq r$ 时的最大值。 2. 给定 $k$ 和 $d$，将下标为 $k$ 的数更改为 $d$。 在操作结束后，他又把数列恢复到执行任何操作之前的状态。也就是说，数列 $a$ 不再受所有 2 类型操作的影响。之后的某一天，他把数列丢了。 幸运的是，Zane 还记得所有操作及其顺序，也记得所有 1 类型操作得到的结果（并且这些结果各不相同）。此外，在所有可能产生相同操作结果的“好”数列中，他知道他的数列 $a$ 的可爱度最大。 数列的可爱度定义为数列中所有整数的按位或运算结果。例如，Zane 的序列 $a$ 的可爱度是 $a_{1} \text{ OR } a_{2} \text{ OR } \ldots \text{ OR } a_{n}$。 Zane 明白，根据他拥有的信息，未必能完全恢复这个数列，因此他愿意接受任何一个“好”数列 $b = b_1, b_2, ..., b_n$，只要它满足： 1. 按相同顺序对它进行同样操作，能得到同样的结果； 2. 它的可爱度等于 Zane 原本的数列 $a$ 的可爱度。 如果存在这样的数列，请你找出并输出，否则认为 Zane 记错了某些信息。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 3 \times 10^5$），分别表示数列的长度和操作次数。 接下来 $m$ 行，每行描述一次操作。第 $i$ 行以一个整数 $t_i$ 开始，表示操作类型。 - 如果 $t_i = 1$，后跟三个整数 $l_i, r_i, x_i$（$1 \le l_i \le r_i \le n$，$0 \le x_i \le 10^9$），表示区间 $[l_i, r_i]$ 的最大值为 $x_i$。 - 如果 $t_i = 2$，后跟两个整数 $k_i, d_i$（$1 \le k_i \le n$，$0 \le d_i \le 10^9$），表示将下标 $k_i$ 的整数赋值为 $d_i$。 保证所有 $t_i = 1$ 的操作结果 $x_i$ 两两不同。 所有操作的给定顺序即为操作实际发生的顺序。

如果不存在合法的“好”数列，输出第一行 `NO`。 否则，输出第一行 `YES`，第二行输出 $n$ 个用空格隔开的整数 $b_1, b_2, ..., b_n$（$0 \leq b_i \leq 10^9$）。 如果有多解，输出任何一个都可以。

在第一个样例中，可以容易地验证这个“好”数列是成立的。特别地，可爱度为 $19 \text{ OR } 0 \text{ OR } 0 \text{ OR } 0 \text{ OR } 1 = 19$。 在第二个样例中，两个操作彼此矛盾，因此不存在这样的好数列。 由 ChatGPT 5 翻译