Rock-Paper-Scissors Champion

题意翻译

$n$ 个人站成一排玩石头剪刀布游戏。从左到右编号为 $1$ 到 $n$。每个人初始有预定的手势，在一轮比赛中不会修改。一轮比赛中，每次你可以安排相邻两个人比赛，胜者留下，败者离开，平局由你来安排谁获胜。直到只剩一个人为冠军，问有多少个人可能成为冠军。 先输入 $n$, $q$， 再给出初始状态，用 ```R``` 表示石头，```S``` 表示剪刀，```P```表示布。 $q$ 次修改， 每次修改一个人的手势，格式为 ```编号 新手势```。 对初始状态和每次修改后的状态输出答案。 $ n, q \le 2 \cdot 10 ^ 5$

题目描述

$ n $ players are going to play a rock-paper-scissors tournament. As you probably know, in a one-on-one match of rock-paper-scissors, two players choose their shapes independently. The outcome is then determined depending on the chosen shapes: "paper" beats "rock", "rock" beats "scissors", "scissors" beat "paper", and two equal shapes result in a draw. At the start of the tournament all players will stand in a row, with their numbers increasing from $ 1 $ for the leftmost player, to $ n $ for the rightmost player. Each player has a pre-chosen shape that they will use in every game throughout the tournament. Here's how the tournament is conducted: - If there is only one player left, he is declared the champion. - Otherwise, two adjacent players in the row are chosen arbitrarily, and they play the next match. The losing player is eliminated from the tournament and leaves his place in the row (with his former neighbours becoming adjacent). If the game is a draw, the losing player is determined by a coin toss. The organizers are informed about all players' favoured shapes. They wish to find out the total number of players who have a chance of becoming the tournament champion (that is, there is a suitable way to choose the order of the games and manipulate the coin tosses). However, some players are still optimizing their strategy, and can inform the organizers about their new shapes. Can you find the number of possible champions after each such request?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ — the number of players and requests respectively ( $ 1 \leq n \leq 2 \cdot 10^5 $ , $ 0 \leq q \leq 2 \cdot 10^5 $ ). The second line contains a string of $ n $ characters. The $ i $ -th of these characters is "R", "P", or "S" if the player $ i $ was going to play "rock", "paper", or "scissors" before all requests respectively. The following $ q $ lines describe the requests. The $ j $ -th of these lines contain an integer $ p_j $ and a character $ c_j $ meaning that the player $ p_j $ is going to use the shape described by the character $ c_j $ from this moment ( $ 1 \leq p_j \leq n $ ).

输出格式

Print $ q + 1 $ integers $ r_0, \ldots, r_q $ , where $ r_k $ is the number of possible champions after processing $ k $ requests.

输入输出样例

输入样例 #1

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

输出样例 #1

2
2
1
2
2
3

题意翻译

$n$ 个人站成一排玩石头剪刀布游戏。从左到右编号为 $1$ 到 $n$。每个人初始有预定的手势，在一轮比赛中不会修改。一轮比赛中，每次你可以安排相邻两个人比赛，胜者留下，败者离开，平局由你来安排谁获胜。直到只剩一个人为冠军，问有多少个人可能成为冠军。 先输入 $n$, $q$， 再给出初始状态，用 ```R``` 表示石头，```S``` 表示剪刀，```P```表示布。 $q$ 次修改， 每次修改一个人的手势，格式为 ```编号 新手势```。 对初始状态和每次修改后的状态输出答案。 $ n, q \le 2 \cdot 10 ^ 5$