公式

F - Range Xor Query 解説 by en_translator


\(a \oplus b\) has \(0\) as an identity and is associative, so it can be processed fast with a segment tree. The time complexity is \(O((N + Q) \log (N))\). Also, if we can calculate \(f(i) = A_1 \oplus A_2 \oplus A_3 \oplus \dots \oplus A_i(f(0) = 0\) fast enough, then the answer will be \(f(Y_i) \oplus f(X_i - 1)\) by the property of xor (where \(f(0) = 0\)), so we can also use Fenwick tree (Binary indexed tree).

Fenwick tree and Segment tree are implemented in AtCoder Library (ACL), which will help you to skip some implementations.

投稿日時:
最終更新: