UOJ Long Round #3 过了就卡卡 solution

zhuzhu2891 · 2025-11-24 09:51:30 · 题解

我们首先写出来一个只需要 n,i,j,k 四个变量的算法。

首先注意到题目保证对于不合法的下标查询，会给出 -1。所以 n 和 i 可以合二为一，直接用 n 来进行遍历。

然后发现由于这是一个排列，所以我们可以直接丢掉 p_1，把它当作 j 来用，反转所有不包含 1 的环，最后再找回 n，然后找回 p_1，并处理第一个数所在的环即可，于是我们就只需要 k 这一个额外变量。

现在观察一下我们的算法发现主要空间瓶颈在于反转一个环的部分。这里我们需要 n,j,k 三个变量来不断往后跳（a_j\leftarrow n,n\leftarrow j,j\leftarrow k,k\leftarrow a_j）。发现这一过程可以改为 \text{swap}(n,a_j),\text{swap}(n,j)，这样我们可以写出只需要一个额外变量进行 swap 操作的代码。

现在我们来尝试掏出一个变量的临时空间，注意到 n 有整整 32 位，而存一个数只需要 19 位。我们滥用一下分支跳转，根据 n 的最高 6 位跳到对应的分支，此时 n 就有 19 位可用，足够我们存下 a_j/j，然后根据 n 里面存的 n 的低 13 位和当前分支编号把 a_j/j 赋值为 n，这样就原地执行了 \text{swap}(i,a_j/j)。

于是全程只使用了免费给出的 n，代码。