CF1085F Rock-Paper-Scissors Champion

有 $n$ 名选手将参加一场石头剪子布锦标赛。你可能知道，在一场一对一的石头剪子布比赛中，两名选手各自独立选择自己的手势。比赛结果根据所选手势决定：“布”胜“石头”，“石头”胜“剪刀”，“剪刀”胜“布”，如果两人出相同的手势则为平局。 比赛开始时，所有选手按顺序站成一排，编号从左到右依次为 $1$ 到 $n$。每位选手都有一个预先选择好的手势，并将在整个比赛中一直使用这个手势。比赛的进行方式如下： - 如果只剩下一名选手，则他成为冠军。 - 否则，任意选择一对相邻的选手进行下一场比赛。失败者被淘汰并离开队列（其原来的邻居变为相邻）。如果比赛为平局，则通过掷硬币决定淘汰者。 主办方已知所有选手的初始手势。他们想知道，有多少名选手有可能成为冠军（即存在一种合理的比赛顺序和硬币结果，使得该选手最终获胜）。然而，有些选手还在调整策略，可能会通知主办方他们的新手势。请你在每次这样的请求后，计算当前有多少名选手有可能成为冠军。

第一行包含两个整数 $n$ 和 $q$，分别表示选手人数和请求数（$1 \leq n \leq 2 \cdot 10^5$，$0 \leq q \leq 2 \cdot 10^5$）。 第二行包含一个长度为 $n$ 的字符串。第 $i$ 个字符为 "R"、"P" 或 "S"，分别表示第 $i$ 位选手原本打算出“石头”、“布”或“剪刀”。 接下来的 $q$ 行，每行包含一个整数 $p_j$ 和一个字符 $c_j$，表示第 $p_j$ 位选手从现在起将使用 $c_j$ 所表示的手势（$1 \leq p_j \leq n$）。

输出 $q+1$ 个整数 $r_0, \ldots, r_q$，其中 $r_k$ 表示处理完第 $k$ 次请求后，有多少名选手有可能成为冠军。

由 ChatGPT 4.1 翻译