読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

yukicoder No. 318 学学学学学

yukicoder セグメント木 遅延セグメント木

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

問題文

http://yukicoder.me/problems/899

解法

....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])

yukicoder No. 318 学学学学学 想定解


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

  • update(l,r,v): 区間[l,r)の値をすべてvに書き換える
  • query(l,r): 区間[l,r)の総和を求める
実装する際は、「値vで区間を塗りつぶす」という情報を遅延伝搬させていく。

yukicoder No. 318 学学学学学 遅延セグメントツリー解

ひとこと

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