けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder EDPC W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!!

一部の競プロ界隈では、俗に実家 DP などと呼ばれてたりしていたものです。

問題概要

01 のみからなる長さ  N の文字列を 0-1 文字列と呼ぶことにします。

今、文字列中の  M 個の連続する区間 ( i 番目の区間 \lbrack l_{i}, r_{i} \rbrack とします) が与えられます。これらの区間を用いて、0-1 文字列  S のスコアは次のように計算されます。

  •  i = 1, 2, \dots, M について
  • 文字列  S区間  \lbrack l_{i}, r_{i} \rbrack の内部に 1 が一個でも存在するならば、スコアに  a_{i} を加算する

0-1 文字列のスコアとして考えられる最大値を求めてください。

制約

  •  1 \le N, M \le 2 \times 10^{5}
  •  -10^{9} \le a_{i} \le 10^{9}

解法

もし  a_{i} がすべて非負であったならば、 S = 111...1 が最適でしょう (その場合のスコアは  \sum_{i = 1}^{M} a_{i} となります)。

実際には  a_{i} が負値となることもありますので、その場合は区間内部はすべて 0 にしておきたいところです。しかしそうしますと、他の正値なスコアを取りこぼしてしまう可能性もあります。このように「全体のバランス」を考えないといけない場合は、DP で解決できる場合が多々あります。

さてこの問題は、結果的に DP 配列自体をセグメント木 (特に Starry Sky Tree) に載せて in-place に更新するような解法で解けます。in-place DP について特集した次の記事で詳しく解説しました。

qiita.com