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

考虑依次将 $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 和树状数组维护即可。