题解：CF1085F Rock-Paper-Scissors Champion

· · 题解

我们把剪刀石头布分别命名为 0，1，2，对于 i，显然其可以打败 i + 1 \bmod 3，会被 i - 1 \bmod 3 打败，注意后文省略取模。我们在修改后分别算每一个的贡献，对于 i 的一个位置 p，其左右两侧分别要么没有 i - 1，要么既有 i + 1 和 i - 1，p 才能构造出合法的胜利方案。这坨东西可以用平衡树维护，每次修改后对三个都算一下，具体细节看代码。做完了。

code