本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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 提交记录