Su0ka game

解説

各操作において、箱の中に果物を入れたあとに $i(1 \leq i \leq N)$ について $i$ の昇順に以下の操作を行えばよいです。

• そのときの $i$ 番目の種類の果物の個数を $c_i$ とする。$c_i$ を $2$ で割った商と余りをそれぞれ $q,r$ とおいたとき、$c_i \rightarrow r , c_{i+1} \rightarrow q+c_{i+1}(i < Nのとき)$ に更新する。

時間計算量は $O(NQ)$ より、低速な言語でなければ実行時間制限に間に合います。

余談

上では配列を用いて解きましたが、操作前後で各種類の果物の数は $0,1$ しかありえないこと、 制約の値が小さいことから2進数の各桁を各種類の果物の数として割り当ててビット演算で実装することもできます。各操作で箱の中に入れた果物の種類 $a_i$ よりも小さい番号の種類の果物の個数は変化しないことから、$a_i$ に対応する桁を $1$ の位として $c_i$ を足し算することで比較的簡単に実装できます。(計算量も改善?)詳しくは実装例をご覧ください。