题解 | #不点两面(hard version)#

某张牌在牌河中的状态变化，只会影响与其距离为 3 的特定位置的“安全状态”。

采用 状态驱动的贡献计数。我们维护一个全局变量 ans 表示当前安全牌的总种数，以及一个频率数组 cnt[] 记录牌河中每种数字的出现次数。

考虑牌 进入或离开牌河时，它仅对以下两个位置的安全性产生直接影响：

1. 位置 ：因为 ，当 在牌河时， 可能变安全。
2. 位置 ：因为 ，当 在牌河时， 可能变安全。

判定准则： 一张牌 是“安全”的，当且仅当：

状态转移

只有当某种牌的计数从 0 变为 1 或者从 1 变为 0 时，安全状态才会发生本质改变。

• 增加 (op=1)：
  1. 如果 cnt[num] 增加前为 0（表示该牌首次进入牌河）：
     • 检查 。如果 ，且此时 本身不满足安全条件（即 也是 0），则 从不安全变为安全，ans++。
     • 检查 。如果 ，且此时 本身不满足安全条件（即 也是 0），则 从不安全变为安全，ans++。
  2. cnt[num]++。
• 移除 (op=2)：
  1. cnt[num]--。
  2. 如果 cnt[num] 减少后变为 0（表示该牌彻底消失）：
     • 检查 。如果 ，且移除后 不再满足任何安全条件（即 也是 0），则 从安全变为不安全，ans--。
     • 检查 。如果 ，且移除后 不再满足任何安全条件（即 也是 0），则 从安全变为不安全，ans--。