#P18827. [Croatian CPC2018] Ghost leg
[Croatian CPC2018] Ghost leg
[Croatian CPC2018] Ghost leg
题目描述
Ghost leg(Amidakuji)是一种抽签游戏, 名玩家各获得 件奖品中的一件。
游戏板上有 条竖线,从左到右编号为 至 。最初还有 条横杆,位于互不相同的高度,从上到下编号为 至 。第 条横杆连接相邻的两条竖线 和 。
第 名玩家位于第 条竖线顶部,第 件奖品位于第 条竖线底部。要确定玩家 获得哪件奖品,从他的起点沿竖线向下走;遇到横杆时,必须沿横杆走到相邻竖线,再继续向下走。最终到达的竖线编号就是奖品编号。
给出游戏板和依次发生的 个事件,每个事件属于以下一种:
A i:移除编号为 的横杆。B j:询问此时玩家 会获得哪件奖品。
请回答所有 B 类询问。
输入格式
第一行包含两个整数 (,)。
第二行包含 个整数 (),按横杆从上到下的顺序描述它们的位置。
第三行包含一个整数 ()。
接下来 行,每行形如 A i()或 B j()。同一条横杆不会被移除两次,且至少有一次 B 类询问。横杆移除后,其他横杆的编号保持不变。
输出格式
按询问顺序,对每个 B 类事件输出一行一个整数,表示对应奖品的编号。
样例 1
输入
6 5
2 1 5 3 2
10
B 1
B 2
B 6
A 3
B 6
B 3
A 1
B 2
B 3
B 4
输出
3
4
5
6
1
1
4
2
样例说明
下图为初始游戏板。玩家 1 经过横杆 2、横杆 5 后获得奖品 3。
