← 返回题目列表

Codeforces · 1085/F

F. 石头剪刀布冠军

中文机器翻译题面 查看原题

$$$n$$$ 玩家将参加石头剪刀布锦标赛。您可能知道,在一对一的石头剪刀布比赛中,两名玩家独立选择自己的形状。然后根据所选形状确定结果:“布”击败“石头”,“石头”击败“剪刀”,“剪刀”击败“布”,两个相同的形状会产生平局。

比赛开始时,所有玩家将站成一排,其数字从最左边玩家的 $$$1$$$ 增加到最右边玩家的 $$$n$$$。每个玩家都有一个预先选择的形状,他们将在整个锦标赛的每场比赛中使用该形状。比赛的进行方式如下:

- 如果只剩下一名玩家,则宣布他为冠军。
- 否则,任意选择该行中的两个相邻玩家,并进行下一场比赛。失败的玩家将从锦标赛中被淘汰,并离开他在该行中的位置(与他的前邻居相邻)。如果比赛是平局,则通过掷硬币决定输家。

组织者了解所有玩家最喜欢的形状。他们希望找出有机会成为锦标赛冠军的玩家总数(即有合适的方法来选择游戏顺序并操纵抛硬币)。不过,一些玩家仍在优化他们的策略,并可以向组织者通报他们的新形状。在每次这样的请求之后,你能找到可能的冠军数量吗?

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ - 分别表示玩家数量和请求数量 ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq q \leq 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 个字符的字符串。如果玩家 $$$i$$$ 在所有请求之前分别要玩“石头”、“布”或“剪刀”,则这些字符中的第 $$$i$$$ 是“R”、“P”或“S”。

以下 $$$q$$$ 行描述了请求。这些行中的第 $$$j$$$ 包含一个整数 $$$p_j$$$ 和一个字符 $$$c_j$$$ ,这意味着玩家 $$$p_j$$$ 从此刻起将使用字符 $$$c_j$$$ 描述的形状 ($$$1 \leq p_j \leq n$$$)。

输出

打印 $$$q + 1$$$ 整数 $$$r_0, \ldots, r_q$$$,其中 $$$r_k$$$ 是处理 $$$k$$$ 请求后可能出现的冠军数量。

示例

输入 #1

3 5
RPS
1 S
2 R
3 P
1 P
2 P

输出 #1

2
2
1
2
2
3