ABC217 参加記録 - geam1113’s diary

コンテスト中AC:A〜E

結合している座標情報を管理する場合、操作列を逆順にしてUnion-Findで結合していくなどが考えられます。しかし、 $L \geq 10^9$ なので、全ての座標を保持することはできません。

そこで、切られた座標を管理することを考えます。

$c_i = 2$ のクエリが来た時、 $x_i$ より左側及び右側で1番近いカット位置をそれぞれ $l_i$ 、 $r_i$ とします。

すると、 $x_i$ が属する丸太の長さは $r_i - l_i$ として求められます。便宜上、 $0,\ L$ にもカットされているものとします。

順序付き集合はc++ならsetで値の挿入、log時間できます。 $r_i$ の探索はupper_boundでlog時間でできます。(今回重複がないので、lower_boundでも可)

$l_i$ の探索は、各座標にマイナスをつけると同じように求められます。

ソート処理は $O(NlogN)$ なので、たくさん出てくると厳しいです。この部分を実際にソートせず処理できないか考えます。

一旦、ソートを挟むと、それまでの出現順は無視され、昇順に並んでいればよいことになります。

そこで、追加順に並んでいる配列 $B$ と、昇順に並んでいる集合 $S$ を別に管理することにします。

そうすると、ソート操作が来た時には、 $B$ の先頭から値を全て取り出し、 $S$ に追加します。

この操作は高々 $Q$ 回しか起こらず、 $S$ をsetにすれば挿入操作はlog時間です。

先頭の値を取り出す操作は、 $S$ が空でないなら $S$ から行い、空なら $B$ から行います。

以上で、ソート操作なしで、各クエリに答えることが可能になりました。