这里补一个 $O(nq)$ 的做法。
暴力 $O(nm)$ 显然是不行的。但我们看到 $q$ 的范围很小,只有 $5000$,所以考虑对每个询问,用 $O(n)$ 或 $O(m)$ 的时间解决掉。
考虑倒推。我们**从后往前**模拟每次置换,求出当前牌在本轮置换以前的位置。这样单次询问的复杂度就做到$O(n)$了。
时间卡的有点紧,吸了口氧跑过去了。
代码很短。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, m, q;
int rep[100005];
inline int read() {
int x = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x;
}
int main() {
n = read(); m = read(); q = read();
for (int i = 1; i <= m; i++)
rep[read()] = i;//rep[i]表示对于一个排列置换后,位置i上原本的数
for (int i = 1; i <= q; i++) {
int x = read(), pl = n - x + 1;
for (int j = n - x + 1; j >= 1; j--)
if (pl <= j + m - 1 && j + m - 1 <= n) pl = j + rep[pl - j + 1] - 1;//模拟倒推
printf("%d\n", pl);
}
return 0;
}
```