C. Sasha and a Bit of Relax 〜累積XOR〜

Quiz

https://codeforces.com/contest/1113/problem/C

AC Code

https://codeforces.com/contest/1113/submission/56527349

解法

f:id:peroon:20190705025450j:plain

  • 上記のように、左端〜右端のXOR=0のものが数える候補
  • 式変形により、もはやcenterを意識する必要がなくなる
  • 任意区間のXORは、累積XORを作っておけばO(1)で求まる
  • 公式解説 https://codeforces.com/blog/entry/65295

注意

cnt[1][0] = 1;
  • これが必要
  • index=-1のところに累積XOR=0が1つ存在しているとすることで、例えばサンプル2
6
3 2 2 3 7 6

にて、[3 2 2 3] (累積XOR=0)を考えた時にカウントアップすることができる