CF1470E Strange Permutation

Alice 有一个排列 $p_1, p_2, \ldots, p_n$。不幸的是，这个排列看起来非常无聊，于是她决定对其进行一些改变。她可以选择若干个不重叠的子区间，并将它们分别翻转。翻转单个子区间 $[l, r]$（即将第 $l$ 个到第 $r$ 个元素翻转）的代价为 $r - l$，一次操作的总代价为所有被翻转子区间的代价之和。Alice 心中有一个整数 $c$，因此她只考虑总代价不超过 $c$ 的操作。 然后她觉得更无聊了，于是把所有通过恰好一次操作可以得到的排列都写了下来。当然，Alice 很聪明，每个能得到的排列只写一次（无论通过多少种方式得到），并且将这些排列按字典序排序。 现在 Bob 想向 Alice 提出一些问题。每个问题如下：Alice 写下的第 $j$ 个排列中的第 $i$ 个数字是多少？由于 Alice 太无聊不想回答这些问题，于是她请你帮忙。

第一行包含一个整数 $t$（$1 \leq t \leq 30$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$c$、$q$（$1 \leq n \leq 3 \times 10^4$，$1 \leq c \leq 4$，$1 \leq q \leq 3 \times 10^5$），分别表示排列的长度、操作的最大总代价和询问的数量。 每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq n$，$p_i \neq p_j$ 当 $i \neq j$），表示初始排列。 接下来 $q$ 行，每行包含两个整数 $i$ 和 $j$（$1 \leq i \leq n$，$1 \leq j \leq 10^{18}$），表示一次询问的参数。 保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$，所有测试用例中 $q$ 的总和不超过 $3 \times 10^5$。

对于每个询问，输出该询问的答案。如果 Alice 写下的第 $j$ 个排列不存在，则输出 $-1$。

在第一个测试用例中，Alice 写下了如下排列：$[1, 2, 3]$、$[1, 3, 2]$、$[2, 1, 3]$。 注意，对于排列 $[3, 2, 1]$，Alice 需要翻转整个数组，代价为 $2$，大于指定的 $c=1$。其他两个排列无法通过题目描述的恰好一次操作得到。 由 ChatGPT 4.1 翻译