本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-26 19:55:03

我们可以用类似点边容斥的东西，也即点的贡献是正的，边的贡献是负的，然后统计区间和，即得到总贡献。

点的贡献是显然的，那么怎么统计边的贡献呢？

边的贡献，来源于开关状态的变化。

考虑在开关管辖大小上根号分治。我们设阈值 $B$，管辖小于 $B$ 的叫做小开关，否则叫做大开关。

开关之间只有三种：对小，对大和大带小。

小开关之间的贡献，可以枚举其管辖范围暴力算；大开关由于只有 $\dfrac N B$ 个，所以可以预处理出每个大开关和哪几个相邻，然后暴力统计就可以了；

小开关和大开关带起来就不一样了。一个大开关对的小开关数量可能很多，因此不能直接做。但是我们可以考虑从小开关那里算贡献。

小开关状态变化的时候，我们枚举了它管辖的所有点；这时候，如果这个管辖的点旁边是个大开关的话，我们就在这个大开关的贡献上加一，表示它状态翻转会增加一条边。

大概就是这样，细节好像不少，写一下。

估计可以到紫了。紫并不恐怖。

更新一下细节。

如果更新的是一个小点，我们就暴力扫它的管辖范围，然后看看构成了多少个新边。同时，如果某个点旁边是一个大开关，我们需要将这个大开关的贡献加上一。

否则如果更新的是大点，我们就先看和它相邻的所有大点，然后看小点维护出来的和它的贡献即可。