ei1903の競プロメモ

競プロの解説など

HOJ 1528 - Monochrome Balls

問題URL

問題概要

$N \ $個のボールが横一列に並んでおり、始めすべてのボールは白く塗られている。
以下のような$ \ Q \ $個のクエリが与えられる。

  • 左から$ \ x_i \ $番目のボールを黒く塗る

各クエリ後のボールについて、白く塗られたボールが連続して最大何個並んでいるか求めよ。

制約

  • $1 \leq Q \lt N \leq 3 \times 10^5$
  • $1 \leq x_i \leq N$
  • $x_i \neq x_j$

解説

連続した白いボールをUnionFindで管理したくなりますが、UnionFindでは削除するという処理ができません。
そこで、クエリをすべて処理し終えた状態から始め、各クエリを逆に処理していきます。
すべて処理し終えた状態においての答えは簡単に求めることができ、クエリは黒く塗られたボールを白く塗りなおす処理とすることができるのでUnionFindで処理が可能です。
よってこの問題は計算量$ \ O(Q \alpha(N)) \ $で解くことが出来ました。
※$ \ a(N) \ $はアッカーマン関数逆関数