問題概要
個のボールが横一列に並んでおり、始めすべてのボールは白く塗られている。
以下のような個のクエリが与えられる。
- 左から
番目のボールを黒く塗る
各クエリ後のボールについて、白く塗られたボールが連続して最大何個並んでいるか求めよ。
制約
解説
連続した白いボールをUnionFindで管理したくなりますが、UnionFindでは削除するという処理ができません。
そこで、クエリをすべて処理し終えた状態から始め、各クエリを逆に処理していきます。
すべて処理し終えた状態においての答えは簡単に求めることができ、クエリは黒く塗られたボールを白く塗りなおす処理とすることができるのでUnionFindで処理が可能です。
よってこの問題は計算量で解くことが出来ました。
※はアッカーマン関数の逆関数
