Bessie洗牌法

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file shufflegold.in Output file shufflegold.out

【题目描述】


Bessie正在练习牌技,她已经熟练地掌握了一种Bessie洗牌法,就是把M(2<=M<=100,000)张牌重新组织,使从上面数的第i张牌变成第P[i]张牌。

现在Bessie正在一张大台子上洗牌,她的这副牌共有N(M<=N<=1,000,000,000)张,编号分别为1~N。她先取最上面的M张,并按照Bessie洗牌法洗过后再放回那撂牌的最上面,然后她把最上面那张牌拿走,正面朝下放在台子上。她将重复这个过程,并不断地将最上面的牌拿走放到另一撂上去,直到无牌可洗为止。当Bessie剩余的牌不足M张时,他将不再进行Bessie洗牌法,而是持续地拿走最上面的牌放到另一摞上去。

Bessie知道这副牌起初是按顺序排放的,即1号牌在最上面,下面是2号牌,……,最底下一张是N号牌。给你Bessie洗牌法的规则,请帮Bessie计算出洗牌完毕后这摞牌中Q(1<=Q<=N,Q<=5,000)个不同位置上牌的编号。

有50%的数据保证N<=100,000。


【输入格式】


第1行有三个数,分别由一个空格隔开,即N,M,Q;

接下来有M行,其中第i行为Bessie洗牌法中第i张牌的新位置P[i](1<=p[i]<=M);

最后有Q行,其中第i行有一个整数q_i,表示第i个询问,你需要计算出从上往下数第q_i个位置上牌的编号,(1<=q_i<=N)。


【输出格式】

输出共有Q行,其中第i行有一个整数,表示从上面数第q_i个位置上牌的编号。

【样例输入】

5 3 5 3 1 2 1 2 3 4 5

【样例输出】

4

5

3

1

2

【提示】


输出解释:

洗牌过程如下 :

[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (2号牌被拿出,面朝下放置)

[3, 1, 4, 5] -> [1, 4, 3, 5] (1号牌被拿出,面朝下放置)

[4, 3, 5] -> [3, 5, 4] (3号牌被拿出,面朝下放置)

[5, 4] (5号牌被拿出,面朝下放置)

[4] (4号牌被拿出,面朝下放置)

最终的顺序为(从上往下) 4, 5, 3, 1, 2


【来源】

在此键入。