CF1511G Chips on a Board

Alice 和 Bob 有一个由 $n$ 行 $m$ 列组成的矩形棋盘。每一行恰好有一个棋子。 Alice 和 Bob 玩如下的游戏。他们选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le m$，并将棋盘裁剪，只保留第 $l$ 列到第 $r$ 列（包含 $l$ 和 $r$）之间的部分。所有在第 $l$ 列左侧和第 $r$ 列右侧的列都不再属于棋盘。 裁剪棋盘后，他们可以在剩下的棋盘部分（即第 $l$ 列到第 $r$ 列）移动棋子。两人轮流操作，无法操作的一方输掉游戏。Alice 先手，Bob 后手，之后轮流。每次操作时，玩家必须选择一个棋盘上的棋子，并将其向左移动任意正整数个格子（也就是说，如果棋子当前在第 $i$ 列，可以移动到任意 $j < i$ 的列；在最左边的列的棋子不能被选择）。 Alice 和 Bob 有 $q$ 对数 $L_i$ 和 $R_i$。对于每一对 $(L_i, R_i)$，他们想知道如果 $l = L_i$ 且 $r = R_i$，谁会赢得游戏。注意，这些游戏彼此独立（不会影响下一个游戏的棋盘状态），且 Alice 和 Bob 都采取最优策略。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^5$），表示棋盘的行数和列数。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le m$），其中 $c_i$ 表示第 $i$ 行的棋子所在的列编号（即第 $i$ 行的棋子在第 $c_i$ 列）。 第三行包含一个整数 $q$（$1 \le q \le 2 \times 10^5$）。 接下来 $q$ 行，每行包含两个整数 $L_i$ 和 $R_i$（$1 \le L_i \le R_i \le m$）。

输出一个长度为 $q$ 的字符串。第 $i$ 个字符应为 'A'，如果 Alice 在 $l = L_i$ 且 $r = R_i$ 时能获胜；否则为 'B'，表示 Bob 获胜。

由 ChatGPT 4.1 翻译