UOJ Long Round #3 过了就卡卡 solution

我们首先写出来一个只需要 $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$，代码。