题解：P14180 「FAOI-R8」奶龙大战暴暴龙

szh_AK_all · 2025-10-07 20:13:33 · 题解

考虑依次将 b 的每个位置与 a 匹配。

具体的，假设对于 b_{1\sim i-1}，我们都已经匹配好了。那么对于 b_i，我们找到满足 j\ge i 且 a_j=b_i 的最小的 j，然后把 a_j 移到 b_i 的位置。怎么移呢？如果 j\ne n，那么把 a_j,a_{j+1} 一起移到 i-1 之后；否则把 a_{i\sim n-1} 一起移到末尾。

当然还有一种特殊情况是 i=n-1,j=n，此时我们需要交换 a_{n-1},a_n 这两个位置。对于 n\le 3 显然无解，但是我们需要特判形如 x,y,x 变为 x,x,y；对于 n\ge 4，我们仅仅需要 4 个数便可以达成此操作。假设当前序列为 4,3,2,1，我们要将它变为 4,3,1,2，那么可以先将 4,3 移到 2 后面，使序列变为 2,4,3,1，再将 4,3,1 移到开头，使序列变为 4,3,1,2。

这样直接做的平方的，足以在赛时通过本题。

可以发现每次把匹配完的点删除之后剩下的数的相对顺序不变，而每次操作会使一个区间的数的位置增加或减少一个值，拿 set 和树状数组维护即可。