説明
- 累積XORとは、累積和と同じように事前計算しておくことで範囲のXORをO(1)で求める方法のこと
XORの性質
- a xor a = 0
- a xor 0 = a
- 上記を利用すると、A = a xor b xor c xor d xor e の値を持っていて c xor d xor e の値が知りたいときは A xor a xor b で求まる
- (同じ値をかけてキャンセルできる)
code
// 累積XOR struct AccXOR{ VI Acc; AccXOR(VI& A){ ll N = A.size(); Acc.resize(N+1); rep(i, N){ Acc[i+1] = Acc[i] ^ A[i]; } } // 閉区間 [a, b] // A[a] ^ ... ^ A[b]を返す ll range(ll a, ll b){ return Acc[b+1] ^ Acc[a]; } };
verified
https://yukicoder.me/submissions/408532
累積XORクラス(2021 ver)
- verified 2021/05/05
// xor ver struct AccXor{ vector<ll> Ac; ll L; AccXor(){} AccXor(vector<ll> &A){ L = A.size(); Ac.resize(L+1); rep(i,L){ Ac[i+1] = Ac[i] ^ A[i]; // 添字は1ずれる } } // sum of [a, b) ll sum(ll a, ll b){ if(a<0){ debug("halt [AccSum]a<0",a);exit(0); return -1; } if(b>L){ debug("halt [AccSum]b>L-1",b,L-1);exit(0); return -1; } return Ac[b] ^ Ac[a]; } };
追記:XORの性質2
- 1325D - Ehab the Xorcist (diff1700)
a⊕b = u a + b = v とする a + b = a⊕b + 2 * (a&b) よって a&b = (v-u)/2 (ここでv, uのパリティは一致しているとする) これにより+と&を変換できることがある +ではなく&にすることでbitごとに考えられる
- 再訪。この問題は手強いが学びも多い