Rock-Paper-Scissors Champion
Contest: Technocup 2019 - Elimination Round 4
Difficulty rating: 2500

$$$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?

Input format:
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$$$).

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 5
RPS
1 S
2 R
3 P
1 P
2 P

Example output:
2
2
1
2
2
3

Editorial:
First, let's determine which players can win in a given configuration. If all players have the same shape, then everyone can win. If there are only two kinds of shapes, then one shape always loses, and everyone with the other shape can win. Let's now assume there are all three shapes present. If a player $$$i$$$ can win, then they have to independently eliminate everyone to either side. It suffices to determine if $$$i$$$ can win everyone to their left (the other side can be treated symmetrically).
Suppose that the player $$$i$$$ has the shape R (all the other cases are similar). We will show that $$$i$$$ can not eliminate everyone to the left if and only if two conditions hold:
• there is no S to the left of $$$i$$$;
• there is at least one P to the left of $$$i$$$.
Indeed, if both of these are true, there is nothing stopping a P from eliminating $$$i$$$. Otherwise, if there are no P to the left of $$$i$$$, he can potentially win everyone there.
Finally, suppose that there is an S to the left of $$$i$$$. Here's how $$$i$$$ can eliminate everyone to the left. First, eliminate all P's as follows: locate the closest pair of P and S, bring them together by eliminating all R's in between with the P, then eliminate the P. When we've eiliminated all P's this way, we are left with the previous case (no P's).
Now, how to deal with modifications? Assume that there are currently all three shapes present (otherwise we can easily find the answer as described at the start). How many R's can not win (similar for P's and S's)? According to our criterion, all R's losing because they can not eliminate their respective left-hand sides are located between $$$P_0$$$ and $$$S_0$$$, where $$$P_0$$$ and $$$S_0$$$ are positions of the first P and S (that is, when $$$P_0 < S_0$$$, otherwise there are no R's losing this way). A similar condition applies to the R's losing because of the right-hand side. Now we simply count the number of R's in these ranges and subtract them from the total. Note that we can never subtract an R twice since there is at one S on one of its sides.
It now suffices to use any data structure that supports range summing and finding extreme values in a set, with modifications. For the range summing we may use a Fenwick tree (BIT) or a segment tree, and for extreme values an std::set will suffice. All operations we need take $$$O(\log n)$$$ time, hence each modification and answer takes $$$O(\log n)$$$ time.