题解 P3095 【[USACO13DEC]贝西洗牌The Bessie Shuffle】
AquaRio
2019-09-30 22:33:48
食用效果更佳：[**我的博客**](http://39.105.95.125/index.php/archives/380/)
既然没有正解，那我就来写一发把。
### 思路:
我们对问题仔细研究，很快就会发现，问题就是给定一个位置 $x$ ，问它经过若干轮置换后会到达哪个位置。
值得注意的是我们需要对置换做出一些调整，因为每次都会删除头部的元素，所以真实的置换是 $p[i]-1$。
举个栗子：
$[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] -> [3,1,4,5]$
在这里面，$p[1]=3$，但是 $1$ 在置换到 $3$ 号位置的时候，$2$ 被弹了出来，所以 $1$ 实际上换到的位置是 $p[1]-1=2$ 。
我们瞄一眼数据范围，$1e5$ 好吓人，我们必须找出一种带有 $\log$ 的方法来求出每一个询问的数置换的最终位置。
灵机一动，**倍增**！
我们设 $a[i][j]$ 表示 $j\ (1 \leq j \leq m) $ 在置换 $2^{i}$ 次后的位置。
于是我们就可以找到最终位置辣 (>_<)
但是要注意当中途走到 $0$ 时，说明离开了队列，应及时终止。
### 代码：
```cpp
/*
Name: P3095 [USACO13DEC]贝西洗牌The Bessie Shuffle
Author: AquaRio
Date: 30/09/19 22:01
State: Accepted
Anti_Copy: Enabled
*/
#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=30;
int n,m,q;
int a[M][N];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-'){f=-1;}ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();m=read();q=read();
for(int i=m;i;i--){
int x=read();
a[0][m-x+1]=i-1;//注意置换是P[i]-1
}
for(int i=1;i<M;i++)
for(int j=1;j<=m;j++)
a[i][j]=a[i-1][a[i-1][j]];//倍增预处理
int x,r,len;
while(q--){
x=read();
if(x<m) r=m;
else r=x,x=m;
len=n-r+1;
for(int i=M-1;~i;i--)
if((1<<i)<=len && a[i][x])
x=a[i][x],len-=1<<i,r+=1<<i;//倍增查找最终位置
if(len) x=a[0][x],r++;//注意弹出去
cout<<n-r+m-x+1<<endl;
}
return 0;
}
```