题解：等价程序 (Equivalent Programs)

题目理解

我们有两个长度相同的程序（指令序列），指令类型为 $1 \dots k$。

某些指令对是互斥的，即它们不能交换位置（交换后程序行为不同）。
其余指令对是可交换的（相邻时可以交换，且交换后程序等价）。

等价的定义：
如果两个程序可以通过一系列相邻可交换指令的交换变成相同的程序，则它们等价。

换句话说，如果两个指令不是互斥对，那么它们在相邻时可以交换，否则不能交换。

问题转化

这个问题可以转化为：

• 将指令抽象为图中的节点。
• 如果两个指令类型是互斥的，则在它们之间连一条边。
• 那么，可交换的指令对就是没有边的指令对。

在序列中，我们可以交换相邻且可交换的指令，等价于在序列中冒泡排序时，只有无边相连的指令可以交换。

因此，两个程序等价 ⟺ 它们可以通过一系列相邻无边指令的交换互相转换。

已知结论（排列等价类）

这是一个经典问题：
如果定义"可交换关系"为无向图的边，那么两个排列属于同一个等价类，当且仅当：

1. 每个值的出现位置集合在排序后相同（即 multiset 相同）。
2. 对于任意互斥对 $(x,y)$，$x$ 在第一个程序中的位置与 $y$ 在第一个程序中的位置之间的顺序关系，与第二个程序中相同。

更形式化地：
对于每个互斥对 $(x,y)$，在第一个程序中，所有 $x$ 与 $y$ 的相对顺序（即 $x$ 在 $y$ 之前还是之后）在第二个程序中必须一致。

代码中的实现

代码中定义：

• a[type] 存储类型 type 在第一个程序中的所有位置（按升序）
• b[type] 存储类型 type 在第二个程序中的所有位置（按升序）

在检查过程中：

1. 首先检查每个类型的出现次数是否相同，不同则直接输出 NIE。
2. 对于每个互斥对 $(x, y)$：
   • 为了减少复杂度，选择出现次数较少的类型作为 $x$。
   • 对于 $x$ 的每一个出现位置 a[x][i]，在 a[y] 中二分查找有多少个 $y$ 的位置在它之前（即 o(a[y], a[x][i]) 表示 $y$ 在 $x$ 之前的数量）。
   • 同样在第二个程序中，对 $b[x][i]$ 在 $b[y]$ 中二分查找 $y$ 在它之前的数量。
   • 如果这两个数量不一致，说明 $x$ 与 $y$ 的相对顺序改变了，输出 NIE。
3. 如果所有互斥对的相对顺序都一致，输出 TAK。

正确性解释

为什么这样是正确的？

因为如果两个程序等价，那么对于任意互斥对 $(x,y)$，它们的相对顺序在冒泡排序（只允许无边交换）过程中是保持不变的。
因此，对于每个 $x$ 的出现，它前面有多少个 $y$ 在两个程序中必须相同。

代码正是检查这个条件：
对于每个互斥对 $(x,y)$ 和每个 $x$ 的位置，计算它前面 $y$ 的数量，在两个程序中必须一致。

复杂度分析

• 存储位置：$O(n)$
• 对每个互斥对，遍历较小出现次数的类型，并二分查找：
  总复杂度 $O(m \cdot \min(size_x, size_y) \cdot \log n)$
  因为 $\sum \min(size_x, size_y) \le n \sqrt{m}$（类似小的合并到大的一些分析），并且 $m \le 50000$，$n \le 10^5$，所以可过。

算法标签

• 图结构
• 组合数学
• 二分查找

时间复杂度

• 预处理位置数组：$O(n)$
• 检查每个互斥对：$O(m \cdot \min(size_x, size_y) \cdot \log n)$
• 对于 $n \leq 100000$, $m \leq 50000$ 是可行的。

代码总结

代码的核心是：

1. 统计每个指令类型在两个程序中的位置分布
2. 检查指令出现次数是否一致
3. 对于每个互斥对，检查相对顺序是否保持不变
4. 利用二分查找高效计算相对位置关系

这样就能高效判断两个程序是否等价。