ABC293G 题解

__vector__ · 2023-03-13 14:17:03 · 题解

本题解作者赛时由于答案输出部分写挂，删点写挂，没能绝杀。

题解

没有修改，且不强制在线，而且可以快速处理加点删点对答案的贡献，显然是莫队板子。
oiwiki 普通莫队算法
说一下具体实现。

考虑加上或删除某个点后，怎么计算贡献。

可以开一个数组记录每个值在原数组出现次数。

设加或删的点值为 val。

• 加点
  设 val 在原来的数组中出现了 cnt_{val} 次。
  答案将增加 C_{cnt_{val}+1}^3 -C_{cnt_{val}}^3 = \frac{cnt_{val}(cnt_{val}-1)}{2}。
  然后更新 cnt_{val} 即可。
• 删点
  若 cnt_{val} \le 2，显然不需要计算。
  否则将答案减少 C_{cnt_{val}}^{3} - C_{cnt_{val}-1}^{3}，我手懒就不把化简后的式子写上了。
  然后更新 cnt_{val} 即可。

Atcoder 提交记录