一、问题重述

给定两个极大数组 $a$（长度 $N$）与 $b$（长度 $M$），数组元素取值在 $[1,k]$ 之间。 Alice 与 Bob 轮流进行如下操作： 向初始为空的序列 $c$ 末尾追加一个数字，使得 $c$ 始终是 $a$ 与 $b$ 的公共子序列。 无法操作者负，Alice 先手。

共 $q$ 次询问，每次给出 $(x_i,y_i)$：

• 切掉 $a$ 前 $x_i$ 个元素，切掉 $b$ 前 $y_i$ 个元素；
• 在剩余的子数组上进行游戏；
• 题目保证剩余部分开头元素相同。

求每次询问中 Alice 是否有必胜策略。

限制： $1\le N,M\le 10^9$，$1\le n,m,k\le 1600$，$1\le q\le 10^6$。 数组以连续等值段形式给出：$a$ 有 $n$ 段，$b$ 有 $m$ 段，相邻段值不同。

---

二、游戏本质分析

因为 $c$ 必须是 $a,b$ 的公共子序列，且只能向后追加，所以：

• 每一步只能选择当前位置之后、在两数组中都存在的下一个公共颜色；
• 合法移动唯一确定：只能沿着相同颜色依次向后走。

这是一个无分支的公平博弈，胜负只取决于最大可操作步数的奇偶性。

---

三、形式化定义

1. 段结构

设：

• $A_i$ 表示 $a$ 的第 $i$ 段，值为 $v_{A_i}$；
• $B_j$ 表示 $b$ 的第 $j$ 段，值为 $v_{B_j}$。

对于询问 $(x,y)$，可以在 $O(\log n)$ / $O(n)$ 内定位到：

• $x$ 落在 $a$ 的第 $i$ 段；
• $y$ 落在 $b$ 的第 $j$ 段。

题目保证 $v_{A_i}=v_{B_j}$。

2. 后继状态

对当前段对 $(i,j)$，令颜色 $u=v_{A_i}=v_{B_j}$。 定义：

• $nx(i)$：$a$ 中第 $i$ 段之后第一个值为 $u$ 的段编号；
• $ny(j)$：$b$ 中第 $j$ 段之后第一个值为 $u$ 的段编号。

若不存在这样的段，则 $nx(i)=n+1$ 或 $ny(j)=m+1$。

3. 胜负状态（Grundy 数）

定义 $dp[i][j] \in \{0,1\}$：

• $dp[i][j]=1$：当前先手必胜（Alice 赢）；
• $dp[i][j]=0$：当前先手必败（Bob 赢）。

转移规则：

$$dp[i][j] = \begin{cases} 1 & nx(i) > n\ \text{或}\ ny(j) > m \\ 1 - dp[nx(i)][ny(j)] & \text{其他情况} \end{cases} $$

直观解释：

• 无法再走时，当前玩家胜；
• 每多走一步，胜负状态翻转一次；
• 最终等价于判断最大可走步数是否为奇数。

---

四、算法结构

1. 预处理连续段前缀和 用于快速将位置 $(x,y)$ 映射到对应段编号 $(i,j)$。

2. 预处理后继段 对每个段 $i$，求 $nx(i)$；对每个段 $j$，求 $ny(j)$。

3. 区间 DP 打表 按段编号从后往前递推，填充 $dp[i][j]$。 复杂度 $O(nm)$，在 $n,m\le 1600$ 时为 $2.56\times 10^6$，完全可接受。

4. 处理大量询问 对每组 $(x,y)$：

   • 定位段 $(i,j)$；
   • 若 $dp[i][j]=1$ 输出 Yes，否则 No。 单次查询 $O(\log n)$ 或 $O(n)$，可支持 $q\le 10^6$。

---

五、正确性证明

1. 公共子序列的扩展路径唯一：只能沿相同颜色顺序前进。
2. 游戏无分支、无选择，是一条链。
3. 链上每一步翻转胜负，因此状态只由后继状态取反得到。
4. 无法扩展时当前玩家获胜，对应边界 $dp=1$。
5. 所有询问满足起点颜色相同，因此状态合法有效。

---

六、复杂度总结

• 预处理：$O(n + m)$
• DP 计算：$O(nm)$
• 单组询问：$O(\log n)$
• 总复杂度：$O(nm + q\log n)$ 可在 $2.5\mathrm{s}$ 内通过全部数据。

---

七、结论

• 若从段对 $(i,j)$ 出发的最长可操作步数为奇数，则 Alice 必胜；
• 若为偶数，则 Bob 必胜；
• 用 $dp[i][j]$ 记录奇偶结果，查询时直接查表即可。