问题重述

我们有一个初始数组 $a$，经过 $q$ 次操作后得到数组 $b$。第 $i$ 次操作是：

$$c_{z_i} := \min(c_{x_i}, c_{y_i})$$

已知最终数组 $b$ 和所有操作 $(x_i, y_i, z_i)$，要求构造一个可能的初始数组 $a$，或判断无解。

---

核心思想：逆向推导约束

我们不知道初始数组 $a$，但知道最终数组 $b$。如果我们从最终状态反向推导，可以得到每个位置 $i$ 在初始时至少应该是多少。

定义 $l_i$ 为位置 $i$ 在某个时刻必须满足的下界。初始时，最终状态要求 $c_i \ge b_i$，所以 $l = b$。

---

反向操作规则

考虑最后一次操作（第 $q$ 次）：

$$c_{z_q} := \min(c_{x_q}, c_{y_q})$$

操作后，我们有 $c_{z_q} \ge b_{z_q}$，且 $c_{x_q} \ge b_{x_q}$，$c_{y_q} \ge b_{y_q}$。

现在我们想知道操作前这些位置的下界。

分析：

• 对于 $i \notin \{x_q, y_q, z_q\}$，这些位置在操作中没有被修改，所以它们的下界不变：$l'_i = l_i$。
• 对于 $z_q$：操作前 $c_{z_q}$ 的值会被覆盖，所以操作前它没有任何限制（可以被任意值覆盖）。因此 $l'_{z_q} = 0$。
• 对于 $x_q$：操作后 $c_{z_q} = \min(c_{x_q}, c_{y_q})$。
  由于 $c_{z_q} \ge b_{z_q}$，我们有 $\min(c_{x_q}, c_{y_q}) \ge b_{z_q}$。
  这意味着 $c_{x_q} \ge b_{z_q}$ 且 $c_{y_q} \ge b_{z_q}$。
  另外，操作后 $c_{x_q}$ 保持不变，所以 $c_{x_q} \ge \max(b_{x_q}, b_{z_q})$。
  同理 $c_{y_q} \ge \max(b_{y_q}, b_{z_q})$。

因此，反向更新的规则是：

$$l'_{x} = \max(l_x, l_z), \quad l'_{y} = \max(l_y, l_z) $$$$l'_z = 0$$

其余位置不变。

---

算法步骤

1. 初始化：设 $l = b$。
2. 逆向遍历操作 $i = q$ 到 $1$：
   • 记当前 $l_{z_i}$ 为 $v$。
   • 将 $l_{z_i}$ 设为 $0$（因为被覆盖）。
   • 更新 $l_{x_i} = \max(l_{x_i}, v)$
   • 更新 $l_{y_i} = \max(l_{y_i}, v)$
3. 得到 $l$ 数组后，令 $a = l$。
4. 正向验证：用 $a$ 作为初始数组，按原操作顺序执行一遍，检查最终结果是否等于 $b$。
   • 如果相等，输出 $a$。
   • 如果不相等，输出 $-1$。

---

为什么这样构造是正确的？

• 必要性：任何可行的初始数组 $a$ 必须满足 $a_i \ge l_i$，否则无法达到 $b$。
• 充分性：取 $a = l$ 是满足条件的最小可能值。如果 $a = l$ 经过正向操作后得到的结果不等于 $b$，说明矛盾，无解。否则，$a = l$ 就是一个解。

---

时间复杂度

• 逆向更新：$O(q)$
• 正向模拟：$O(q)$
• 总复杂度：$O(n + q)$ 每个测试用例。

---

代码实现

// 逆向求出下界 l（存储在 c 数组中）
for(int i = q ; i >= 1 ; i --){
    int v = c[z[i]];      // 当前 l[z_i] 的值
    c[z[i]] = 0;          // 被覆盖，下界变为 0
    c[x[i]] = max(c[x[i]], v);   // 更新 x_i 的下界
    c[y[i]] = max(c[y[i]], v);   // 更新 y_i 的下界
}

// a = l
for(int i = 1 ; i <= n ; i ++) a[i] = c[i];

// 正向模拟验证
for(int i = 1 ; i <= q ; i ++) 
    c[z[i]] = min(c[x[i]], c[y[i]]);

// 检查是否与 b 一致
for(int i = 1 ; i <= n ; i ++) 
    if(b[i] != c[i]) {
        cout << "-1\n";
        return;
    }

---

示例验证

样例1：

n=2, q=1, b=[1,2]
操作: (2,1,2)

逆向：

• 初始 $c = [1,2]$
• $i=1$: $v = c[2] = 2$，$c[2] = 0$，$c[1] = \max(1, 2) = 2$ 得 $a = [2, 0]$ 正向：
• $c[2] = \min(c[2], c[1]) = \min(0, 2) = 0$，最终 $c = [2, 0] \neq [1,2]$，输出 -1。

样例2：

n=3, q=2, b=[1,2,3]
操作1: (2,3,2)
操作2: (1,2,1)

逆向：

• 初始 $c = [1,2,3]$
• $i=2$: $v = c[1] = 1$，$c[1]=0$，$c[1]=\max(0,1)$，$c[2]=\max(2,1)=2$
• $i=1$: $v = c[2] = 2$，$c[2]=0$，$c[2]=\max(0,2)$，$c[3]=\max(3,2)=3$ 得 $a = [1,2,3]$ 正向模拟不改变数组，匹配 $b$，输出 1 2 3。

---

总结

本题的关键是逆向推导下界，然后正向验证。这种方法利用了 $\min$ 操作的性质，通过最大值传递约束，最终构造出最小可行解。如果最小解都不满足，则无解。