筒の中のボールの状態をランレングス符号化を行って保持します。

つまり、例えば

1 2 3
1 3 4
1 10 10

というクエリの後の筒の状態を、「\(2\) が \(3\) 個、\(3\) が \(4\) 個、\(10\) が \(10\) 個」という形で保持します。クエリ \(1\) 回につき、このリストの長さは高々 \(1\) しか増えないため、クエリ処理全体を通して長さが \(Q\) を超えることはありません。

この形式の情報を deque で持つことにすれば、挿入クエリは \(O(1)\)、取り出しクエリは \(O(1+(\text{dequeから削除した要素の個数}))\) となります。したがって、全体の計算量は \(O(Q)\) で問題を解くことができました。

なお、この問題では、厳密にランレングス符号化を行わなくとも AC を得ることができます。例えば

1 10 3
1 10 10

というクエリの後の筒の状態をランレングス符号化すると「\(10\) が \(13\) 個」となりますが、単に「\(10\) が \(10\) 個、\(10\) が\(3\) 個」としても全体の計算量は \(O(Q)\) となります。