mahjong solution

· · 题解

mahjong solution

O(nm) 做法

第一步也是很重要的一步，因为有平局，所以我们应当先钦定平局算 Bob 胜利，这样如果 Alice 还能胜利那么答案是 Alice；再钦定平局算 Alice 胜利，这样如果 Bob 还能胜利那么答案是 Bob；否则答案是 Draw。

先进行观察，我们首先可以发现点炮的和牌是行不通的，要和一定是自摸，也就是对手不会打给你你当前有的牌。接下来我们发现，当两个玩家目前手牌相同时，他们只能一直摸切，直到有人自摸或平局。也就是这类情况我们可以直接判定获胜的人。

再观察，如果某一方将一张牌 A 一直握在手里，考虑下一张 A 出现时的情况。不妨设下一张 A 在 x 时刻出现。那么如果下一张 A 就是此人摸到，那么一直握着这张 A 的收益就是在 x 时刻直接获胜。否则双方会进入上述的摸切环节，那么考虑再下一张 A 是谁摸到，如果是自己，那么收益还是在 x 时刻直接获胜；如果是对方，那么收益是在 x 时刻直接失败。注意如果根本没有下一张牌，那么这张牌的收益就是啥也没有；如果有下一张牌但没有再下一张，那么根据平局算谁胜来判断对应收益。

因此对于每张牌，我们可以计算出它对应的收益，也就是一直拿着它，你会在第几轮立刻获胜，还是在第几轮立刻输掉，还是啥事没有。我们再声称游戏的胜负仅和握的牌产生的收益相关。例如如果有一局你打出一张牌恰好等于对手的手牌，那么这个应当已经在对手的这张牌的收益中进行计算。所以我们直接扫一遍序列，维护当前两个人持有的手牌，每次贪心选择更优的手牌，如果当前时刻有人的手牌收益产生，那么判定胜负。

一个小细节需要注意：如果双方初始手牌相同，那么立刻进入摸切环节，只需要判断下一张这个牌是谁摸上来就行，需要特判这种情况。

O((n+m)\log n) 做法

在用数据结构维护上述过程中一个麻烦的问题是，对于收益是在某回合立刻输掉的牌，操作者的方案是选择回合较大的牌留下，而这样不满足二分性并且不方便用数据结构维护。但是我们可以继续观察性质：假设当前为第 x 回合，该玩家两张手牌都是收益是在某回合输掉的牌，注意到首先这两个回合一定都大于 x，且一定和 x 的奇偶性不同，而且这两个回合还一定不相等，所以至少有一张牌会在 x+2 回合以上输掉，那么保留这张牌，每回合都这么做，就会永远不会因为收益是在某回合立刻输掉的牌而输掉。所以我们根本不用管这些输掉的牌。

一个细节是，如果 Bob 的初始手牌是收益是在某回合立刻输掉的牌，由于 Bob 一开始没有选择权，所以这张牌是有可能导致一回合后 Bob 立刻输掉的，这种情况需要特判。

那么我们只要关注收益是在某回合获胜的牌。要是我们能找到区间内所有这样的牌，我们只需要找到导致获胜回合最小的那张，显然只需要判断这张牌属于谁就行。考虑随着 r 端点的移动，每张牌的收益发生的变化：假设这张牌和其后两张相同牌出现位置分别为 x,y,z，那么当 r\in[x,y] 时，这张牌没有收益；当 r\in[y,z] 时，这张牌收益为平局的收益；当 r\in[z,n] 时，这张牌收益根据 z 的奇偶性决定。所以每张牌收益会变化 O(1) 次，我们在扫描 r 的时候动态维护，然后每次查询就是区间最小值，线段树维护即可。

最后一步也可以扫描 l，然后观察到每种牌只有最近 3 张有效，从而数据结构维护。当然也有一些其他维护方法，这里不再赘述。