yukicoder No. 318 学学学学学

(2015/12/12 2:04) 問題を勘違いしていたので一部修正しました。

....t..t...t...のように1が複数個あったとしても、書き換えに影響するのは一番端にあるtだけ。そこで最初と最後を区間としてみることにする。そうするとb[i]の値はiを覆うtの最大値になる。

ある値xが最初に現れる位置がiならl[i]=x、最後に現れる位置がiならr[i]=x、それ以外のl[i]、r[i]はNILとしておけば、次のような処理でb[i]を決めていける。

for i in xrange(n):
    if l[i] != NIL: set.add(l[i])
    b[i] = max(set)
    if r[i] != NIL: set.remove(r[i])

ちなみにこの問題は遅延セグメントツリーで殴れる。遅延セグメントツリーで次の操作ができるデータ構造を作ればいい。

実装する際は、「値vで区間を塗りつぶす」という情報を遅延伝搬させていく。

yukicoderで遅延セグメントツリーの練習するならこの問題が一番簡単かもしれない。