Codeforces Round #687(Div.1) B - XOR-gun
メモ。
問題概要
単調非減少な数列Aが与えられる。この数列に対して、次の操作を繰り返し行い、単調非減少ではない状態にしたい。
・ 隣接する二つの要素を取り除き、そこに二つの要素の排他的論理和を挿入する。
必要な操作回数は最低何回か？（数列Aを長さ1になるまで操作しても達成できない場合-1）
解法
明らかに、あるi,i+1,i+2について、MSB(a[i]) == MSB(a[i+2])ならば、a[i] > (a[i+1] xor a[i+2])。よって答えは1である。これにコンテスト中気づけなかった。痛い...。
その上で、操作後の数列Cを考えると、全てのCの要素は、Aの連続部分列の排他的論理和であることより、
rng_xor(int l,int r) := (a[l] xor a[l+1] xor ... xor a[r-1])
とした時、rng_xor(l,r) > rng_xor(r,k) ならば、添字組{l,l+1},{l+1,l+2},...,{r-2,r-1},{r,r+1},...,{k-2,k-1}に対して操作を施すことで所望の数列が得られる。この時、答えを(k - l - 2)で更新する。
ACコード：
