No.038 C

これも B 問題と同じく grundy 数を考える.

豆はすべて独立に動くので, $i$ 番目の茶碗にある1つの豆の grundy 数を考え, それを茶碗ごと豆の数ごとに排他的論理和を取る. すなわち, 豆の数は偶奇しかみなくていい.

これで部分点1, 2が取れるはずである.

さて, 愚直に grundy 数を計算すると $O(N^2)$ かかる.

そこで, インデックスに grundy 数を, 値としてその grundy 数が最後に現れた茶碗の位置を持つ RMQ を考える.

このとき, 区間 $[0, x]$ の最小値が $i - C_i$ より大きい場合, $x$ 以下の grundy 数はすべて使われていることになる. よって, 区間 $[0, x]$ の最小値が初めて $i - C_i$ 未満となる $x$ を探せば, それが $i$ 番目の grundy 数となる.

RMQ はセグメントツリーで管理する.