提供一种思路，可以做到\(O(n)\)。
目前是全OJ最优解，跑到了79ms。
update 2023.07.29 完工，期望无bug（暑假快乐吖o(￣▽￣)ブ）
update 2023.07.27 （要原题检测了，先占个坑，有时间再补）
原题大意
P3095 [USACO13DEC] The Bessie Shuffle S
有\(n\)张牌，每次取出\(m\;(m<n)\)张牌进行置换操作。操作完一轮后会出第\(1\)张牌，并再加入\(1\)张牌继续进行新一轮的置换操作。
最后无法再进行操作时，则按现顺序不断出牌。求倒数第\(x\)次出牌的原编号是多少。
暴力解法
如果没有思考直接开码的话，得到的暴力代码是\(O(nq)\)的。这个时间复杂度2013年的老机器是过不了的。
但是wangziye就是暴力+玄学优化+快读+卡常+优秀的DYOJ评测机在考场暴切了这道紫题。经过计算，他的代码时间复杂度不到\(O(nq)\)，最坏情况大概1000ms多一点点。
Orz%%%。
预计：\(73pts\)
倍增解法
这是正解的一种。通过倍增优化后，时间复杂度是\(O(n \log n)\)。
此处不展开讲倍增解法，原因有三：
- 本题的
分析一栏，教练已经写了倍增解法的题解。 - 虽然是\(O(n \log n)\)，可以通过本题，但还不是最优解，本帖主要讲最优解\(O(n)\)做法。
本人只会不熟练的运用倍增求LCA问题（虽然现在还是用树链剖分求LCA），倍增还能优化是我听教练讲解后才知道的。
预计：\(100pts\)
\(O(n)\)解法
[warning]：前方请准备好草稿纸，有演算过程……
Part 0 思考性质
首先我们考虑普通的置换。
例如下面的这个情景：
有5个学生要换位置。
\[1\;2\;3\;4\;5 \]
原位置：目标位置：
\[4\;3\;1\;5\;2 \]推论：如果我们把原位置上的数与目标位置上的数进行建边，会得到一些（可能一个）环或点。
\[1\to 4\to 5\to 2\to 3\to 1 \]
如上例：多举几个例子，会发现都符合推论。
那我们再来看本题的置换。
但是本题的置换有一个很大的特色——每次置换后都会推出第\(1\)个数，加入第\(m+1\)个数。
这样的特色带来了一个性质：那就是本题置换不会出现环，只会出现链。
为什么呢？因为有一个都被推出了，相当于下一次的置换就再也找不到那一个。因此不会形成环。
那现在，就对我们的置换操作，来分些Part吧。
Part 1 “直接走”操作
为什么叫“直接走”？这个操作用来得到被推出来的\(n-m+1\)张牌。
\(n-m+1\)是因为最多只会做\(n-m+1\)次置换。
因此，可以用dfs染色的方法先把含\(1\)的链得出。那么按dfs顺序得到的一些\(x_i\)代表着正数第\(i\)次原编号为\(x\)的牌就被推出了。
但是要一点要注意，因为有的时候置换的操作不多，所以可能有一些残留的、与答案不符的。
所以需要做个判断，假设得到的\(x\)数组长度为\(len\)。
- 若\(len< n-m+1\)，则将\(x_i\)其中\(i\in [1,len]\)一个一个地压入答案的\(ans[]\)数组里。
- 否则，直接将\(i\in [1,n-m+1]\)的所有\(x_i\)压入\(ans[]\)即可。
但是，第一种情况时，还有一些\((n-m+1-len)\)的元素还没压入怎么办？如何考虑这些元素？
请移步Part 2
Part 2 “直接走没走完”操作
这里，我们如何思考？
考场上，可以通过打表法来观察。即我们手搓样例，再模拟出牌过程。
[warning]：如果你不想思考、不想自己动手，可以直接跳到一个结论部分。
这里可以提供一组样例，十分建议大家手搓一下：
输入
10 5 10
4
1
3
5
2
10
9
8
7
6
5
4
3
2
1
输出
2
3
1
5
6
7
10
8
9
4
这个样例，是属于“直接走没走完”的情况。因为含\(1\)的链，只有
\[2\to 3\to 1\to 5 \]这也正是样例输出的前四个。
但是\(n-m+1=10-5+1=6\)，现在只得到了“直接走”部分的前\(4\)个，还有俩没输出呢，怎么办？
仔细看看样例输出，\(6\)和\(7\)是接下来的这俩。
有啥规律吗？如果你再多搓几组样例，就会发现一个结论。
一个结论
\[x_i=m+i\;\;\;\;\; i\in [len+1,n-m+1-len] \]但是道理是什么？
因为我们这\(m\)个位置的置换可以分成两部分：
- 从入口\(0\)到\(m\)的一条链（路径）
- 其余部分
而这个其余部分是各种大小不一的环，而置换后，本质上数的位置就是环中不断变换的位置。
结论已出，那此Part结束。现在，我们剑指Part 3。
Part 3 “走不完”操作
为什么叫“走不完”？
因为剩下的部分数量$< m $无法进行置换操作。故称“走不完”。
此处要注意的是，有些人一开始会认为：“这些牌做不了置换，那就没有发生过位置变动，直接一个一个按原顺序压入\(ans[]\)好了。”
错误的。
因为有一些部分“经历过”置换，可能是被换过来的。所以上面的说法并不正确。
那这一部分怎么处理呢？
先假设从入口\(0\)到\(m\)的链（路径）长度为\(l\)。
因为这是最后的\(m-1\)个数，所以链（路径）中留下来的就是最后进入链（路径）的\(l-1\)个数。因为没有第\(m\)个数了（数量都\(< m\) 了嘛），意味着没有新的数加入进来。其余位置也就是环了（这里解释过，在Part 2末），那么可以用同余的方式得出每个位置上的数。
Part 4 查询操作
那现在，我们把置换分成的这3个部分全分析清楚了，那么出牌顺序就可以存下来\(ans[]\)。询问的时候，\(O(1)\)输出就好了。
时间复杂度：\(O(n)\)
预计：\(100pts\)
代码实现
虽然时间复杂度降下来了，但是这个方法的思考难度、实现难度都比倍增法更难一些。
所以这里贴一份全代码，各位奆奆洁身自好、不要COPY。
此处贴一份原题检测时AC的代码，因为是原题检测，为了手速就丢掉快读、快写了。79ms的评测代码是加了快读、快写的。
评测下来是90ms，这仍比\(O(n\log n)\)的倍增做法快了不止一点。
[warning]：码风丑的话喷轻一点（逃
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int MAXN=1e5+5;
int n,m,q;
int p[MAXN],f[MAXN];
int tot,cnt,len=-1;
int rk[MAXN];
int col[MAXN],ans[MAXN],b[MAXN],c[MAXN];
bool vis[MAXN];
struct node
{
vector<int> v;
}a[MAXN];
void dfs(int x,int co)
{
if(col[x]) return;
if(co==1)
b[++len]=x;
col[x]=co;
rk[x]=a[co].v.size();
a[co].v.pb(x);
if(x>=m) return;
dfs(f[x+1],co);
}
void work1(int x)
{
if(col[x]==1)
{
if(rk[x]>=n-m+1)
c[a[1].v[rk[x]-n+m-1]]=x;
}
else
{
int co=col[x];
int l=a[co].v.size();
c[a[co].v[((rk[x]-n+m-1)%l+l)%l]]=x;
}
}
void work2(int x,int y)
{
if(vis[x]) return;
if(rk[m]>=y)
c[a[1].v[rk[m]-y]]=x;
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=1;i<=m;i++)
scanf("%lld",&p[i]),f[p[i]]=i;
for(int i=0;i<=m;i++)
if(!col[i])
dfs(i,++tot);
if(len<n-m+1)
{
for(int i=1;i<=len;i++)
ans[++cnt]=b[i];
for(int i=1;i<=n-m+1-len;i++)
ans[++cnt]=m+i,vis[m+i]=1;
}
else for(int i=1;i<=n-m+1;i++)
ans[++cnt]=b[i];
for(int i=1;i<=m;i++)
work1(i);
for(int i=m+1,j=n-m;i<=n;i++,j--)
work2(i,j);
for(int i=1;i<m;i++)
ans[++cnt]=c[i];
while(q--)
{
int x;
scanf("%lld",&x);
printf("%lld\n",ans[n-x+1]);
}
return 0;
}