F. Sequence Recovery

Zane 曾经有一个 _good_ 序列 #cf_span[a]，包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] — 但他已经丢失了它。 一个序列被称为 _good_，当且仅当它的所有整数均为非负且不超过 #cf_span[109]。 然而，Zane 记得他曾对他的序列应用了 #cf_span[m] 次操作。 有两种类型的操作： 1. 给定 #cf_span[l] 和 #cf_span[r]，找出满足 #cf_span[l ≤ i ≤ r] 的所有下标 #cf_span[i] 对应整数的最大值。 2. 给定 #cf_span[k] 和 #cf_span[d]，将下标为 #cf_span[k] 的整数赋值为 #cf_span[d]。 在完成操作后，他将序列恢复到任何操作应用前的状态。也就是说，序列 #cf_span[a] 不再受类型 2 操作的影响。然后，他在某个时间点丢失了该序列。 幸运的是，Zane 记住了所有操作及其应用顺序，以及所有类型 1 操作的 *不同* 结果。此外，在所有能产生相同结果（当以相同顺序应用相同操作时）的 _good_ 序列中，他知道他的序列 #cf_span[a] 具有最大的 _cuteness_。 我们定义一个序列的 _cuteness_ 为该序列中所有整数的按位或结果。例如，Zane 序列 #cf_span[a] 的 _cuteness_ 为 #cf_span[a1] _OR_ #cf_span[a2] _OR_ ... _OR_ #cf_span[an]。 Zane 明白，仅凭他的信息可能无法完全恢复丢失的序列，因此他希望得到任意一个 _good_ 序列 #cf_span[b]，包含 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn]，满足： 1. 当以相同顺序应用相同操作时，会产生相同的结果； 2. 具有与 Zane 原序列 #cf_span[a] 相同的 _cuteness_。 如果存在这样的序列，请找出它。否则，说明 Zane 的记忆有误，这是可能的。 第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 3·105]) — 分别表示 Zane 原序列中整数的个数和应用的操作数。 接下来的 #cf_span[m] 行中，第 #cf_span[i] 行以一个整数 #cf_span[ti] 开头（#cf_span[ti ∈ {1, 2}]）— 表示第 #cf_span[i] 次操作的类型。 如果操作是类型 1（#cf_span[ti = 1]），则后续跟随三个整数 #cf_span[li], #cf_span[ri], 和 #cf_span[xi] (#cf_span[1 ≤ li ≤ ri ≤ n], #cf_span[0 ≤ xi ≤ 109]) — 分别表示考虑的最左下标、最右下标，以及下标在 #cf_span[li] 到 #cf_span[ri]（含）之间的所有整数的最大值。 如果操作是类型 2（#cf_span[ti = 2]），则后续跟随两个整数 #cf_span[ki] 和 #cf_span[di] (#cf_span[1 ≤ ki ≤ n], #cf_span[0 ≤ di ≤ 109]) — 表示在此操作后，下标为 #cf_span[ki] 的整数应变为 #cf_span[di]。 保证对于所有满足 #cf_span[1 ≤ i < j ≤ m] 且 #cf_span[ti = tj = 1] 的数对 #cf_span[(i, j)]，都有 #cf_span[xi ≠ xj]。 操作按它们被应用的顺序给出。也就是说，先给出的操作先被应用，依此类推。 如果不存在合法的 _good_ 序列，请在第一行输出 "_NO_"（不含引号）。 否则，在第一行输出 "_YES_"（不含引号），并在第二行输出 #cf_span[n] 个空格分隔的整数 #cf_span[b1, b2, ..., bn] (#cf_span[0 ≤ bi ≤ 109])。 如果有多个答案，输出任意一个即可。 在第一个样例中，容易验证该 _good_ 序列是合法的。特别是，其 _cuteness_ 为 #cf_span[19] _OR_ #cf_span[0] _OR_ #cf_span[0] _OR_ #cf_span[0] _OR_ #cf_span[1] #cf_span[ = ] #cf_span[19]。 在第二个样例中，两个操作明显矛盾，因此不存在这样的 _good_ 序列。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 3·105]) — 分别表示 Zane 原序列中整数的个数和应用的操作数。接下来的 #cf_span[m] 行中，第 #cf_span[i] 行以一个整数 #cf_span[ti] 开头（#cf_span[ti ∈ {1, 2}]）— 表示第 #cf_span[i] 次操作的类型。如果操作是类型 1（#cf_span[ti = 1]），则后续跟随三个整数 #cf_span[li], #cf_span[ri], 和 #cf_span[xi] (#cf_span[1 ≤ li ≤ ri ≤ n], #cf_span[0 ≤ xi ≤ 109]) — 分别表示考虑的最左下标、最右下标，以及下标在 #cf_span[li] 到 #cf_span[ri]（含）之间的所有整数的最大值。如果操作是类型 2（#cf_span[ti = 2]），则后续跟随两个整数 #cf_span[ki] 和 #cf_span[di] (#cf_span[1 ≤ ki ≤ n], #cf_span[0 ≤ di ≤ 109]) — 表示在此操作后，下标为 #cf_span[ki] 的整数应变为 #cf_span[di]。保证对于所有满足 #cf_span[1 ≤ i < j ≤ m] 且 #cf_span[ti = tj = 1] 的数对 #cf_span[(i, j)]，都有 #cf_span[xi ≠ xj]。操作按它们被应用的顺序给出。也就是说，先给出的操作先被应用，依此类推。 ## Output 如果不存在合法的 _good_ 序列，请在第一行输出 "_NO_"（不含引号）。否则，在第一行输出 "_YES_"（不含引号），并在第二行输出 #cf_span[n] 个空格分隔的整数 #cf_span[b1, b2, ..., bn] (#cf_span[0 ≤ bi ≤ 109])。如果有多个答案，输出任意一个即可。 [samples] ## Note 在第一个样例中，容易验证该 _good_ 序列是合法的。特别是，其 _cuteness_ 为 #cf_span[19] _OR_ #cf_span[0] _OR_ #cf_span[0] _OR_ #cf_span[0] _OR_ #cf_span[1] #cf_span[ = ] #cf_span[19]。 在第二个样例中，两个操作明显矛盾，因此不存在这样的 _good_ 序列。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the length of the sequence and number of operations, respectively. Let $ A = (a_1, \dots, a_n) $ be the original (lost) good sequence. Let $ \mathcal{O} = (o_1, \dots, o_m) $ be the sequence of operations, where each $ o_i $ is: - Type 1: $ (l_i, r_i, x_i) $ — query: $ \max_{j \in [l_i, r_i]} a_j = x_i $ - Type 2: $ (k_i, d_i) $ — update: $ a_{k_i} \gets d_i $ Let $ \mathcal{Q} \subseteq \{1, \dots, m\} $ be the set of indices of type-1 operations. Let $ X = \{x_i \mid i \in \mathcal{Q}\} $ be the set of distinct query results. Let $ B = (b_1, \dots, b_n) $ be a candidate good sequence ($ 0 \le b_j \le 10^9 $). **Constraints** 1. For each type-1 operation $ i \in \mathcal{Q} $: $$ \max_{j \in [l_i, r_i]} b_j = x_i $$ 2. For each type-2 operation $ i \notin \mathcal{Q} $: $$ b_{k_i} = d_i \quad \text{(applied in order, but sequence is restored to pre-update state)} $$ → **Crucially**: Type-2 operations are *applied and then undone*; the sequence $ A $ (and thus $ B $) is **unaffected** by them. → Therefore, **type-2 operations impose no constraints** on $ B $. 3. $ 0 \le b_j \le 10^9 $ for all $ j \in \{1, \dots, n\} $ 4. The cuteness of $ B $ must equal that of $ A $: $$ \bigvee_{j=1}^n b_j = \bigvee_{j=1}^n a_j $$ **Objective** Find any sequence $ B = (b_1, \dots, b_n) $ satisfying constraints 1–4, or output "NO" if none exists. **Note**: Since $ A $ is the sequence *before any updates*, and type-2 operations are undone, only type-1 constraints matter for $ B $. The cuteness of $ A $ is unknown, but we are told that $ B $ must match it. However, since $ A $ is unknown, we **must reconstruct** the minimal possible cuteness consistent with the type-1 constraints, and then construct $ B $ to achieve exactly that cuteness. → The **maximum possible cuteness** consistent with the type-1 constraints is the OR of all query maxima $ \bigvee_{i \in \mathcal{Q}} x_i $. → The **minimum possible cuteness** is also this value, because to satisfy $ \max_{[l_i,r_i]} b_j = x_i $, at least one element in each interval must be $ x_i $, and thus the OR must include all bits in any $ x_i $. Therefore, the cuteness of any valid $ B $ **must** be: $$ C = \bigvee_{i \in \mathcal{Q}} x_i $$ We must construct $ B $ such that: - For each type-1 operation $ i $: $ \max_{j \in [l_i, r_i]} b_j = x_i $ - $ \bigvee_{j=1}^n b_j = C $ - $ 0 \le b_j \le 10^9 $ **Constructive Strategy**: For each position $ j \in \{1, \dots, n\} $, define: $$ b_j = \bigvee \{ x_i \mid i \in \mathcal{Q},\ j \in [l_i, r_i] \} $$ Then, for each query $ i $, since $ x_i $ appears in the OR of some $ b_j $ in $ [l_i, r_i] $, and $ b_j \le x_i $ for all $ j \in [l_i, r_i] $ (because $ x_i $ is the max), we must ensure $ \max b_j = x_i $. But: $ b_j $ as defined above may be **greater than** $ x_i $ if $ j $ is covered by multiple queries with larger $ x_i $. → So we must **constrain** each $ b_j $ to be at most the **minimum** $ x_i $ over all queries covering $ j $. Define: $$ M_j = \min \{ x_i \mid i \in \mathcal{Q},\ j \in [l_i, r_i] \} \quad \text{(if no query covers } j, \text{ then } M_j = 0) $$ Then set: $$ b_j = M_j $$ Now: - $ b_j \le x_i $ for all $ i $ covering $ j $ → satisfies max constraint - For each query $ i $, there must exist some $ j \in [l_i, r_i] $ with $ b_j = x_i $ → otherwise max < $ x_i $, contradiction But: if for some query $ i $, all $ j \in [l_i, r_i] $ have $ M_j < x_i $, then $ \max b_j < x_i $ → invalid. So we must check: For each query $ i $, does there exist $ j \in [l_i, r_i] $ such that $ M_j = x_i $? → If yes for all queries, then $ b_j = M_j $ is valid, and: $$ \bigvee_{j=1}^n b_j = \bigvee_{i \in \mathcal{Q}} x_i = C $$ → If no for some query, output "NO". **Final Formal Statement** **Definitions** Let $ n, m \in \mathbb{Z}^+ $. Let $ \mathcal{Q} = \{ i \in \{1, \dots, m\} \mid t_i = 1 \} $ be the set of type-1 operation indices. For each $ i \in \mathcal{Q} $, let $ (l_i, r_i, x_i) $ be the query parameters. **Constraints** For each $ j \in \{1, \dots, n\} $, define: $$ M_j = \begin{cases} \min \{ x_i \mid i \in \mathcal{Q},\ l_i \le j \le r_i \} & \text{if } \exists i \in \mathcal{Q} \text{ s.t. } j \in [l_i, r_i] \\ 0 & \text{otherwise} \end{cases} $$ For each $ i \in \mathcal{Q} $, require: $$ \max_{j \in [l_i, r_i]} M_j = x_i $$ **Objective** If the above constraint holds for all $ i \in \mathcal{Q} $, then output $ B = (M_1, \dots, M_n) $. Otherwise, output "NO".