题意理解

给定 $n$ 个未知正整数 $a_1, a_2, \dots, a_n$ 和 $m$ 条约束条件，每条约束形如：

$$a_i + a_j + a_k - \max(a_i, a_j, a_k) - \min(a_i, a_j, a_k) = x $$

需要构造满足所有约束的序列，或者判断无解。

核心思路

关键观察 1：数学化简

约束条件中的表达式：

$$a_i + a_j + a_k - \max(a_i, a_j, a_k) - \min(a_i, a_j, a_k) $$

实际上就是三个数的中位数。

证明：设三个数排序后为 $p \leq q \leq r$，则：

• $\max = r$，$\min = p$
• 原式 = $p + q + r - p - r = q$（中位数）

因此每条约束等价于：$a_i, a_j, a_k$ 的中位数等于 $x$。

关键观察 2：约束转化

对于三个数 $a, b, c$ 满足中位数为 $x$，等价于：

• 至少有两个数 $\geq x$
• 至少有两个数 $\leq x$
• 其中一个数必须等于 $x$

更精确地说，排序后的三个数 $(p, q, r)$ 满足 $q = x$。

关键观察 3：图论建模

将问题转化为图论问题：

• 每个变量 $a_i$ 对应图中的一个节点
• 每条约束 $(i, j, k, x)$ 可以转化为节点之间的边权关系
• 特别地，如果 $i = j = k$，则直接确定 $a_i = x$

算法框架

方法一：差分约束系统

将约束转化为不等式：

• 对于约束 $(i, j, k, x)$，设三个数排序后为 $p \leq q \leq r$ 且 $q = x$
• 这意味着：$p \leq x \leq r$
• 且 $p, r$ 中至少一个等于 $x$（当三个数不全相等时）

可以建立差分约束系统，但需要小心处理等号情况。

方法二：并查集 + 值域限制

1. 初始化：每个变量初始值域为 $[1, 10^9]$
2. 处理约束：
   • 如果 $i = j = k$，则 $a_i$ 必须等于 $x$
   • 否则，约束表明三个数中至少有一个等于 $x$
   • 用并查集维护相等关系
   • 更新每个连通分量的值域范围
3. 矛盾检测：如果某个连通分量的值域为空，则无解
4. 构造解：为每个连通分量在值域内任选一个值

方法三：贪心赋值

1. 处理确定值：先处理所有 $i = j = k$ 的约束，直接确定变量值
2. 传播约束：对于每个约束 $(i, j, k, x)$：
   • 如果其中两个变量已确定，可以推导出第三个变量的取值范围
   • 如果其中一个变量等于 $x$，则约束自动满足
3. 迭代更新：重复传播直到所有变量确定或发现矛盾

特殊情况处理

自环约束

当 $i = j = k$ 时，约束简化为 $a_i = x$，直接确定该变量值。

重复变量

当 $i = j \neq k$ 时，约束简化为：

• 如果 $a_i \leq a_k$，则 $a_i = x$
• 如果 $a_i \geq a_k$，则 $a_k = x$
• 实际上意味着 $\min(a_i, a_k) = x$

复杂度分析

• 朴素实现：$O(n + m)$ 或 $O(n \log n + m)$
• 需要维护：变量的值域范围、相等关系
• 约束传播：可能需要多轮迭代

构造策略

如果存在解，可以采用以下策略构造：

1. 确定基础值：处理所有直接相等的约束
2. 拓扑排序：根据约束关系确定赋值顺序
3. 贪心赋值：在满足所有约束的前提下，为每个变量选择尽可能小的值
4. 验证检查：最终验证所有约束是否满足

总结

本题的关键在于：

1. 识别中位数：将复杂表达式简化为中位数计算
2. 约束转化：将中位数约束转化为变量的值域限制和相等关系
3. 矛盾检测：在约束传播过程中及时发现无解情况
4. 构造算法：在满足所有约束的前提下构造具体解

这是一个典型的约束满足问题，需要综合运用图论、数学和构造技巧。