abc 098 D - Xor Sum 2 (python)

尺取り法：数列の連続した部分列にあてはまる条件を O(n) で求めてくれる優れもの。
XOR四天王の二人目を倒しました。(弱さも多分2番目)
個人的な尺取り法の実装については、条件を満たさなくなった瞬間に（部分列の長さ - 1）を使って求めたいものを求めて、最後まで見終わったら、続いている部分列の長さを使ってできる答えを足したらいいかなとなりました。
部分列の先頭から順に取り出すのを、前もって数にその数列での位置を紐づけして heap にいれることで解決している。
XORの基本は、a XOR a = 0 となることぐらい？
なので尺取り法で余分な部分を捨てるときに、和の方は
cs = a + b + c + d から a,b を取り除きたいときは cs -= (a+b) としたらよく
XORだと cc = a^b^c^d から cc = cc^a^b とすればいい
また連続する部分列の長さが L と分かればそこで追加される組は L*(L+1)//2 となる
部分列の先頭が変わったときに、変更前と変更後で重複している部分列の長さだけ引く必要があることに注意
むしろそのデバッグに30分以上かかった。頭の中だけで考えるよりおとなしく紙とかに書いた方がいいね...

from heapq import heapify,heappush,heappop
n = int(input())
a = [int(i) for i in input().split()]

p = 0; ans = 0; cc = 0; cs = 0
chk = []
heapify(chk)
for i,ai in enumerate(a):
  heappush(chk,(i,ai))
  cc = cc^ai
  cs += ai
  ans += 1
  if cc != cs : # 条件を満たさなくなったら、
    p += (ans-1)*(ans)//2 # 部分列の長さ - 1 を使って求めたいものを求める
    while chk:
      j,aj = heappop(chk)
      ans -= 1
      cc = cc^aj
      cs -= aj
      if cc == cs:
        p -= (ans-1)*(ans)//2
        cnt = 0
        break
p += ans*(ans+1)//2 # 最後まで見終わったら、続いている部分列の長さを使ってできる答えを足す
print(p)