CF1037G A Game on Strings

Alice 和 Bob 正在玩一个关于字符串的游戏。 一开始，他们有一个字符串 $t$。每一回合，当前玩家选择 $t$ 中的某个字符 $c$，并删除 $t$ 中所有的 $c$，这样 $t$ 会被分割成若干个更小的字符串。之后，游戏会在每个字符串上独立进行——每次操作，玩家选择其中一个字符串和其中的一个字符，删除该字符的所有出现，并将剩下的字符串重新加入游戏。 Alice 总是先手，然后 Alice 和 Bob 轮流操作。无法进行操作（因为没有字符串剩下）的一方判负。 他们过去总是用同一个字符串 $s$ 作为初始字符串，但最近觉得这样太无聊了。现在，每局游戏前，他们会选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le |s|$，并用字符串 $s_l s_{l+1} s_{l+2} \ldots s_r$ 作为初始字符串进行游戏。 给定字符串 $s$ 以及每局游戏的 $l$ 和 $r$，请你判断每局游戏谁会获胜，假设双方都足够聪明并且采取最优策略。

第一行包含字符串 $s$（$1 \le |s| \le 10^5$），仅包含小写英文字母。这是 Alice 和 Bob 用来开始游戏的字符串。 第二行包含一个整数 $m$（$1 \le m \le 10^5$），表示需要分析的游戏局数。 接下来的 $m$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le |s|$），表示每局游戏的初始子串在 $s$ 中的区间。

对于每一局游戏，输出一行，内容为获胜者的名字——"Alice" 或 "Bob"。

在第一个样例中： 1. 第一局选择的字符串是 "aa"。Alice 删除字符 'a'，Bob 无法继续操作。 2. 第二局选择的字符串是 "aaab"。无论 Alice 删除哪个字符，Bob 都会删除另一个字符，Alice 无法继续操作。 在第二个样例中，Alice 都能赢下 "bdb" 和 "aaccbdb" 这两局。 对于 "bdb" 这局，Alice 可以删除字符 'd'，游戏会分别在 "b" 和 "b" 上独立进行。Bob 删除其中一个字符串，Alice 删除另一个，Bob 无法继续操作。 对于 "aaccbdb" 这局，Alice 可以删除字符 'd'，游戏会分别在 "aaccb" 和 "b" 上独立进行。可以证明，无论双方如何操作，剩下的游戏总共只能进行 $4$ 步，因此 Bob 无法继续操作。 由 ChatGPT 4.1 翻译