-
请把数据加强到 \(\sum n \leq 10^8\) 后重新思考。
-
我们维护全局中被标记的所有点的异或和。发现对于一次 \(1\) 操作，相当于让答案异或上区间的 \(a_i\) 异或和，因为这会让被标记的点变成没被标记的，而没被标记的点会产生贡献。
-
查询的话直接查询即可
-
复杂度 \(O(n)\)
CF1872E Data Structures Fan 题解
发布时间 2023-10-31 21:41:47作者: FOX_konata
请把数据加强到 \(\sum n \leq 10^8\) 后重新思考。
我们维护全局中被标记的所有点的异或和。发现对于一次 \(1\) 操作，相当于让答案异或上区间的 \(a_i\) 异或和，因为这会让被标记的点变成没被标记的，而没被标记的点会产生贡献。
查询的话直接查询即可
复杂度 \(O(n)\)