AT_joi2021_yo2_a.往復すごろく (Round Sugoroku)

JOI 高中的葵购买了一款新的双六棋盘。这款双六棋盘由 $N+2$ 个格子横向排列而成。这些格子从左到右依次编号为 $0$ 到 $N+1$。初始时，格子 $0$ 和格子 $N+1$ 上写有 X，格子 $i$（$1 \leq i \leq N$）上写有 $S_i$。其中，$S_i$ 是字符 . 或 #。

葵用这款双六棋盘和一个棋子进行游戏。最开始，棋子被放置在格子 $A$（$1 \leq A \leq N$）上，面朝右方。此时，$S_A$ 一定是 .。每经过 $1$ 秒，棋子会按当前朝向移动到相邻的一个格子。

该双六棋盘有如下规则：

• 当棋子停在写有 X 的格子上时，棋子的朝向会反转。
• 当棋子停在写有 . 的格子上时，什么都不会发生。
• 当棋子停在写有 # 的格子上时，棋子的朝向会反转，并且该格子上的字符会被改为 .。因此，之后棋子再停在这个格子上时，朝向不会再反转。

此外，棋子的反转和字符的更改所需时间可以忽略不计。

给定双六棋盘和棋子的初始状态，请编写程序计算所有写有 # 的格子都被消除所需的时间。

输入从标准输入按以下格式给出：

$N$ $A$ $S$

其中，$S$ 是一个长度为 $N$ 的字符串，第 $i$ 个字符（$1 \leq i \leq N$）为 $S_i$。

请输出使所有写有 # 的格子都被消除所需的秒数。

限制条件

• $2 \leq N \leq 200\,000$。
• $1 \leq A \leq N$。
• $S_i$ 是字符 . 或 #（$1 \leq i \leq N$）。
• $S_A$ 是字符 .。
• 至少存在一个 $i$（$1 \leq i \leq N$），使得 $S_i$ 是 #。

子任务

1.（40 分）$N \leq 3\,000$。
2.（60 分）无额外限制。

样例解释 1

随着时间的推移，双六棋盘的状态如下所示。右向棋子用 > 表示，左向棋子用 < 表示。

1. X.#>#..#X
2. X.#.<..#X
3. X.#<...#X
4. X.>....#X
5. X..>...#X
6. X...>..#X
7. X....>.#X
8. X.....>#X
9. X......

样例解释 2

随着时间的推移，双六棋盘的状态如下所示。

1. X>#.#X
2. X.<.#X
3. X<..#X
4. >...#X
5. X>..#X
6. X.>.#X
7. X..>#X
8. X...

由 ChatGPT 4.1 翻译