cnblogs。

考场上，在不会特殊性质的情况下，可以先考虑暴力，不仅有保底分，而且方便对拍。

测试点 1,2

大力枚举两个人接下来会出什么牌即可。期望得分 \(8\) 分。

测试点 3 至 5

和普通博弈论题目一样，考虑使用动态规划。状态设计和转移平凡，也可以使用记忆化搜索。期望得分 \(20\) 分。

做完暴力，观察题目描述以及样例，不难发现如下性质：

• 放炮（也就是出一张和另外一个人手牌中颜色一样的牌）是不可能的，这是因为 Alice 和 Bob 都希望自己可以和牌并获胜，若自己无法和牌就会尽可能阻止对方和牌。
• 题目保证了 \(l\) 为奇数，所以每个人将抽到什么牌是固定的。

测试点 11

只有两个颜色，因此直接分类讨论，如果手里颜色相同就看谁会先抽到指定牌堆里那个相同颜色的牌，如果不相同，那么先看 Alice 会抽到什么牌，如果和手里的一样就直接和牌，不一样就将那张不一样的打出去，问题转化成手里颜色相同的情况。实现的时候使用二分查找即可。期望得分 \(24\) 分。

测试点 16

测试点 \(11\) 的第一种情况，同样使用二分查找即可。期望得分 \(28\) 分，考场上这个分数是相当可观的，如果前面的题目不能太过保证的话回去检查前面的题目是一个非常不错的选择。

测试点 1 至 10

根据测试点 \(11\) 和 \(16\) 的提示，我们考虑使用分类讨论下的贪心来解决问题。

由于题面中要求双方采取最优策略，因此有可能会出现有玩家发现自己已经不能胜利，使用尽力得到平局结果的情况。所以需要先假定平局算 Alice 胜，若 Bob 仍能胜出才算 Bob 胜；假定平局算 Bob 胜，若 Alice 仍能胜出才算 Alice 胜；否则，算平局。接下来分类讨论：

• 若双方手牌相同，显然他们将进入摸切（摸到什么出什么）的环节，直到一方自摸。
• 若双方手牌不同，他们会考虑在一个时刻摸到一张合适的牌之后，一直捏着它直到胜利，并且如果摸到的牌会使得自己胜，那么越早越好；若会败，则越晚越好。

那么我们就需要计算一直捏着一张牌会在什么时刻产生定胜负的局面。如果自己捏着一张牌，我们需要考虑下一张牌和再下一张牌的位置对答案的影响。设摸到下一张牌的时刻是 \(x\)。

• 若下一张牌自己摸到，说明自己直接在 \(x\) 时刻胜利了。

• 若对方摸到，问题又转化成了测试点 \(16\) 的情况，此时双方不能丢掉自己的手牌。因此只需要计算下一张牌被谁摸到了即可，胜负判断仍然在 \(x\) 时刻。

  • 若再下一张牌自己摸到，说明在 \(x\) 时刻自己胜利了。

  • 若对方摸到，说明在 \(x\) 时刻自己失败了。

  • 若不存在再下一张，算平局。

直接模拟这个过程即可，个人码量 \(1.8 \text{ KiB}\)。该算法时间复杂度 \(O(nm)\)，算上测试点 \(11\) 和 \(16\) 期望得分 \(48\) 分。实际多过了一个测试点 \(12\)，得 \(52\) 分，一般在考场上做到这个分数就可以回去检查前面的题目了。

测试点 11 至 25

考虑快速获得结果。一般有两种方案：单次询问快速处理，或者离线处理多个询问。

根据题意，我们可以通过一定的观察，发现我们不需要维护接下来会使得自己输掉的牌。

证明：假设当前是第 \(x\) 回合，Alice 的手牌会使得她在回合 \(a\) 失败，并且她又摸到了一张会使得自己在回合 \(b\) 输掉的牌。显然，一定有 \(a>x,b>x,a \not = b\)，且 \(a\) 与 \(b\) 都跟 \(x\) 的奇偶性不相同，即 \(|a-x| \mod 2=1, |b-x| \mod 2=1\)。因此，有至少一张牌是在 \(x+2\) 回合以后才会败，丢掉另一张牌就可以保证自己不会立即失败。

注意需要特判 Bob 初始手牌会使得他立即输掉的情况。

根据这个性质，我们只需要获得最早使得自己胜利的牌的信息即可，最早胜利的牌就是每个区间内最小值所在位置。这样就可以离线询问，从左向右遍历 \(r\)。我们发现区间内产生贡献的牌最多 \(3\) 张，因此我们需要一个支持单点修改，区间查询最小值位置的数据结构，线段树可以完美解决这个问题。

该算法时间复杂度 \(O((n+m) \log n)\)。