← 返回题目列表

Codeforces · 2087/C

C. 硬币游戏

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

有一些硬币排成一排,从左到右编号为$$$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$$$ 的硬币玩游戏,则第一个玩家可以收集的硬币数量。

示例

输入
复制

BGSSBGB
5
1 7
2 6
1 5
3 3
4 7

输出
复制

5
3
3
1
3

注意

让我们考虑一下示例中的查询:

  • 在第一个查询中,所有硬币都在游戏中。最优玩法可以如下进行:第一个玩家拿走所有铜币,第二个玩家拿走所有金币,最后,第一个玩家拿走所有银币。然后第一个玩家将收集$$$5$$$硬币;
  • 在第二个查询中,从第 $$$2$$$-nd 到第 $$$6$$$-th 的硬币都在游戏中。最优玩法可以如下进行:第一个玩家拿走所有银币,第二个玩家拿走所有金币,最后,第一个玩家拿走所有铜币。然后第一个玩家将收集$$$3$$$硬币;
  • 在第三个查询中,从第 $$$1$$$-st 到第 $$$5$$$-th 的硬币都在游戏中。最优玩法可以如下进行:第一个玩家拿走所有银币,第二个玩家拿走所有铜币,最后,第一个玩家拿走所有金币。然后第一个玩家将收集$$$3$$$硬币;
  • 在第四个查询中,游戏中只有 $$$3$$$-rd 硬币。第一个玩家可以立即拿走并结束游戏。