配点: 100 点
問題文
JOI高中生葵购买了新的双六。这个双六是
它具有水平排列的 N+2 正方形形状。这些方格按照从最左边的方格到最右边的方格的顺序填充。
它们的编号最大为0 如果要将其更改为输出最多为 N+1 。起初,质量 0 和正方形 N+1 有 X 是质量 i (1 \leqq i \leqq N) 是
写入 S_i 。然而,S_i 是一个字符 . 或
如果 # 是。
葵是这个双六 1 我正在演奏两首曲子。一开始,棋子是正方形的。 A (1 \leqq A \leqq N) 面向右侧。然而,S_A 是一个字符 . 。葵是 1 每秒将棋子朝其面向的方向移动。 1 移动方块。
这个双六有以下内容规则 设置。 当棋子落在写有
X的方块上时,棋子的方向就会反转。 即使棋子落在写有.的正方形上,也不会发生任何事情。 当棋子落在写有#的方块上时,棋子的方向就会反转。这时,这个方格上写的字符是 将其更改为.。因此,即使此后棋子落到这个方格上,方向也不会逆转。
请注意,翻转碎片和更改字母所需的时间可以忽略不计。
考虑到双六和棋子的初始状态,
编写一个程序,求直到所有写有# 的方块消失所需的时间。
制約
- 2 \leqq N \leqq 200\,000.
- 1 \leqq A \leqq N.
- S_i 是一个字符
.或 如果#(1 \leqq i \leqq N). - S_A 是一个字符
.是。 - S_i 是一个字符
#似乎是 i (1 \leqq i \leqq N) 至少 1 有两个。
小課題
- (40 点) N \leqq 3\,000.
- (60 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N A S
但是,S 是长度 字符串 N 。 i 文字目 (1 \leqq i \leqq N)是 S_i 是。
出力
在标准输出上,
计算所有带有# 的方块消失需要多少秒。
输出为 1 行。
入力例 1
7 3 .#.#..#
出力例 1
8
随着时间的推移,双六的状态发生如下变化。然而,朝右的棋子所在的方格是 >,放置朝左棋子的方格
由 < 代表。
-
X.#>#..#X -
X.#.<..#X -
X.#<...#X -
X.>....#X -
X..>...#X -
X...>..#X -
X....>.#X -
X.....>#X -
X......<X
因此,8 以秒为单位
所有写有 # 的方块都会消失,所以8 。
入力例 2
4 1 .#.#
出力例 2
7
随着时间的推移,双六的状态发生如下变化。
-
X>#.#X -
X.<.#X -
X<..#X -
>...#X -
X>..#X -
X.>.#X -
X..>#X -
X...<X
因此,7 以秒为单位
所有写有 # 的方块都会消失,所以7 。
入力例 3
6 6 #####.
出力例 3
35