题意简述
有 $n$ 个点形成一个环，每个点有 $m$ 个参数，第 $i$ 个物品的第 $j$ 个参数为 $a_{i,j}$ ，我们可以维护一个标记集合，其中标记集合 $(j,v)$ 表示第 $j$ 个参数必须为 $v$ ，初始为空。可以进行以下 $4$ 种移动
- 向右移动至最近的满足所有标记的点，不存在就回到它本身
- 向左移动至最近的满足所有标记的点，不存在就回到它本身
- 添加一个标记，同时移动到包括它本身在内最近的满足所有标记的点，不存在则操作非法
- 删除一个标记
对任意的 $(i,j)$ ，求出 $i$ 到 $j$ 的最小操作次数
$n \le 1000 ,m \le 4,1 \le a_{i,j} \le n$
思路分析
首先显然当前状态下的标签集合一定要满足当前点的条件，于是我们枚举起点，暴力建图跑 $\text{bfs}$ ，具体地，设 $dis_s(u,s)$ 表示从起点 $s$ 出发，初始集合为空，到点 $u$ ，标签集合为 $s$ 的最少操作次数，然后直接模拟建图。
经过观察，我们发现：第三类操作带来的边是 $O(n^2)$ 的，直接复杂度是 $O(n^32^mm)$ 左右的，考虑优化。
我们发现延续之前的思路，这个东西几乎优化不了，因为从一个固定起点出发， $3$ 类操作的后继点是无序的，而我们发现，朴素做法的瓶颈在于：很多状态已经被访问过了，我们枚举出边时还是会枚举到，这造成了大量的浪费，于是我们思考：是否存在一种枚举方式，使得我们可以不重不漏地枚举所有 $3$ 操作的出点，且避开已经访问的状态？
因此，不妨考虑反向来做。我们枚举终点，操作 $1,2,4$ 对称地维护就行，回头看操作 $3$ 我们发现了一个很好的性质：当我们从当前的状态 $s$ 逆向到 $t=s \setminus \{{j}\} (j \in s)$ 时，这个时候合法的前驱点是一个环上的连续区间。证明：设当前状态为 $(u,s)$ ，记左边最近的与 $u$ 在集合 $s$ 中所有参数相同的点为 $x$ ，这个时候：
- 对于 $x$ 左边的点，它们状态添加为 $s$ 时，会先经过 $x$ ，因此不会经过 $u$ ；
- 对于 $x$ 本身，它已经满足 $s$ 中的所有条件，因而不会经过 $u$ ；
- 对于环上在 $u$ 和 $x$ 之间的点，由 $x$ 的定义，中间不存在和 $u$ 在集合 $s$ 中所有参数都相同的点，特别地，这些点的第 $j$ 位参数必然与 $u$ 不同（否则它会满足完整集合 $s$ ，与 $x$ 是左边最近的 $s$ 链点矛盾），因此这些点加上 $u$ 第 $j$ 位的标记后会移动到 $u$ 。
到这一步，自然的想法是线段树优化建图，但是有一种更巧妙的做法：我们用并查集维护当前状态的下一个合法的前驱，被入队过后，将其指向它左边最近的和 $u$ 在第 $t$ 位状态相等的点，这个是可以简单预处理出来的，然后再在 $\text{bfs}$ 跑第三类操作时，我们可以直接遍历链上还未访问过的点，再用路径压缩优化一下。由于每个点最多在操作 $3$ 中被遍历一次，因此这一部分的复杂度是均摊 $O(n\alpha(n))$ 的，$\alpha(n)$ 是并查集，实际运行中常数很小。
综上，我们的时间复杂度是 $O(n^22^mm\alpha(n))$ 的，实现精细足以通过此题。