CF2087C.Coin Game

有一些硬币排成一行，从左到右编号为 $1$。这些硬币有三种类型：金币、银币和铜币。

有两名玩家进行游戏，轮流操作，第一个玩家先手。每一回合，玩家选择三种硬币中的一种，然后收集所有该类型且尚未被另一名玩家拿走的硬币。游戏持续到所有硬币都被收集完为止。两名玩家都采取最优策略，并且都希望自己获得的硬币数量最大。

你的任务是回答 $q$ 个独立的询问：如果只使用编号从 $l$ 到 $r$ 的硬币进行游戏，第一个玩家最多能收集多少枚硬币。

第一行包含一个字符串 $s$（$1 \le |s| \le 10^5$），由字符 G、S 和/或 B 组成。G 表示金币，S 表示银币，B 表示铜币。

第二行包含一个整数 $q$（$1 \le q \le 10^5$），表示询问的数量。

接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le |s|$）。

对于每个询问，输出一个整数，表示如果只用编号从 $l$ 到 $r$ 的硬币进行游戏，第一个玩家最多能收集多少枚硬币。

我们来看示例中的几个询问：

• 第一个询问，所有硬币都参与游戏。最优策略如下：第一个玩家先拿走所有铜币，第二个玩家拿走所有金币，最后第一个玩家拿走所有银币。这样第一个玩家能收集 $5$ 枚硬币；
• 第二个询问，参与游戏的是第 $2$ 到第 $6$ 枚硬币。最优策略如下：第一个玩家先拿走所有银币，第二个玩家拿走所有金币，最后第一个玩家拿走所有铜币。这样第一个玩家能收集 $3$ 枚硬币；
• 第三个询问，参与游戏的是第 $1$ 到第 $5$ 枚硬币。最优策略如下：第一个玩家先拿走所有银币，第二个玩家拿走所有铜币，最后第一个玩家拿走所有金币。这样第一个玩家能收集 $3$ 枚硬币；
• 第四个询问，只有第 $3$ 枚硬币参与游戏。第一个玩家可以直接拿走它，游戏结束。

由 ChatGPT 4.1 翻译