CSP-S 2021 T3 Palin 题解

CSP-S 2021 T3 回文 palin 题解

给定一个 \(2*n\) 个数字的序列，每个数字都在 \(\{1,2,3,...,n\}\) 内，并且出现且仅出现两次。

求一个操作序列，使得其满足按序取出的数字序列为回文序列。操作分为两种：

<code>L</code>：将原序列左端点处的数取出加入新序列尾部，并将原序列左端点处的数删除。

<code>R</code>：将原序列右端点处的数取出加入新序列尾部，并将原序列右端点处的数删除。

多测，数据组数 \(T\leq 100\)，\(1\leq n,\sum n \leq 2\times 10^5\)。

首先必然考虑第一次操作。无论如何操作，我们都能找到与第一次取出的数 \(x\)（\(x\) 必然在左端点和右端点中取一个） 相同的数。我们不妨假设我们在下标 \(i\) 出找到了另外一个 \(x\)。

手玩下样例：

这里我们第一次取出的是左端点，那么我们找到与左端点相同的那个数 \(4\)，它的下标正好也在第 \(4\) 位。

并且，正因为我们第一次取出的是 \(4\)，因此我们显然必须将内部第 \(i\) 位的那个 \(4\) 放在最后一位取出。

与此同时，我们得到了把这两个 \(4\) 给搞定的操作：

由于从左端点取出了一个 \(4\)，那么第一步操作为 <code>L</code>。

由于最终的这个 \(4\) 无论如何都是在只有一个元素的序列中取出的，那么答案无论怎么变都是 <code>L</code>。

搞定了这两个 \(4\) 我们接着来看剩下的序列。

由于每次只能取剩下的左端点和右端点，所以这里只能取 \(1\) 和 \(5\) 中间的一个。

我们发现这里另外 \(1\) 根本不在中间那个 \(4\) 的左右，而如果这一步取 \(1\)，那么倒数第二步必然得取 \(1\)，那么最后几步将无法操作。

考虑取一下 \(5\)，我们发现 \(5\) 在 \(4\) 旁边，那么这一步取 \(5\) 就是非常合法的，（至少对于现在已经处理的前两步和倒数两步而言）。

这里我们来思考一下这两个 \(5\) 是由什么样的操作得到的：

由于从右端点取出了一个 \(5\)，那么第二步操作为 <code>R</code>。

由于从 \(4\) 的右边取出了另外一个 \(5\)，考虑最终剩下来应该长成什么样，大概是：<code>4 5</code> 这样，那么倒数第二步也应该是 <code>R</code>。

这时候应该找到一些规律了。但我们接着把这个样例讲完，剩下：

发现右端有一个 \(3\)，\(5\) 右边有一个 \(3\)，那么把这两个 \(3\) 给取出来。这两步应该都是 <code>R</code>。

左端点和 \(3\) 的右边都是 \(1\)，因此都取出来，这两步应该一个是 <code>L</code>，一个是 <code>R</code>。

这个时候取两个 <code>L</code> 就行。

观察上面的手模过程，我们发现：

每一步可以确定两个位置及其操作。

从第二步开始，每个数必然只能从内部已经取过的数的两边来扩展。

形象地来说，内部已经取过的数字可以构成一根“线段”。

由于第一步无法确定从左开始取还是从右开始取，分类讨论即可。

这两个性质无论对于第一步为 <code>L</code> 还是对于第一步为 <code>R</code> 都是成立的。通过这两个性质我们可以 \(O(1)\) 的计算出一个序列下一步的操作。

另外，如果一个序列在经过若干次扩展后无法继续扩展，那么无解，因为优先扩展左边和右边对于其余部分无影响，如果能够扩展就一定会在某一时刻进行扩展。

具体实现呢？

首先，对于第一步分类讨论，找到左端点或右端点所对应的内部点（最后一个被取出来的位置），打上标记。我们不妨称其为 \(\operatorname{inner}\)。

接下来我们同时维护四根指针：

\(\operatorname{outl}\) 和 \(\operatorname{outr}\)，负责维护在执行完前继操作后两端端点在原序列中的位置。

\(\operatorname{inl}\) 和 \(\operatorname{inr}\)，负责维护在执行完前继操作后内部已操作线段的两端端点在原序列中的位置。

在执行完每一步操作后对这四根指针进行更新。我们优先进行 \(\operatorname{outl}\) 对于 \(\operatorname{inl}\) 和 \(\operatorname{inr}\) 的匹配，原因是输出字典序最小的。

注意如果在某一时刻 \(\operatorname{inl}\leq\operatorname{outl}\)，那么不能继续扩展，否则会将已经扩展过的部分再反向扩展一遍。