EDPC W - Intervals

区間

考え方

ABCでいうと、F問題級。

まず、計算量が $O((M+N)N)$ くらいかかってもいい前提で考えてみる。
区間がたくさんある問題なので、区間スケジューリング問題のように、$r$ の値でソートする。

DP テーブルとして、以下を用意する。（$j$ は 1-indexed とする）

はじめは、区間が $1$ つも採用されていない状態であり、全てが $0$ である。
ここに、$r$ の値が小さい順に、区間を追加していく。

$1$ つ区間を追加すると、DP テーブルは以下のように処理することになる。

といっても、$r$ よりも右の部分は毎回上書きする意味もあまりないので、実質以下のようになる。
ただし、 $3$ つめの最大値は $2$ つめの処理前に取るものとする

これは、前のマスから順に、以下のように処理するようにすると簡単である。

これで $O((M+N)N)$ 解ができた。

これを高速化する。
DP テーブルに対して行うことは、区間最大値の取得と、範囲への加算。
よって、区間加算と区間最大値取得ができる lazy segment 木でインライン DP にすればよい。
計算量は $O((N+M)\log N)$ となる。

入力を受け取る。

n: 5
m: 3
(l, r, a):
  (1, 3, 10)
  (2, 4, -10)
  (3, 5, 10)

seg[j] を、得点に絡むうち最も右にある $1$ が j 番目である場合の最大得点とする。
seg[0] は、まだ $1$ がない場合を表す。

最初は、まだ何も選んでいないので次の状態である。

seg[0] = 0

右端 $r$ ごとに区間をまとめておき、$i$ を左から右へ動かしながら処理する。
各 $i$ では、まず新しく $i$ 番目を $1$ にする状態を作る。
これは、これまでの状態の最大値を seg[i] に入れることで表せる。

$i=1$ では、seg[0] から seg[1] を作る。
この時点で $r=1$ の区間はない。

seg: {0, 0}

$i=2$ でも同様に、これまでの最大値から seg[2] を作る。
この時点で $r=2$ の区間はない。

seg: {0, 0, 0}

$i=3$ では、まず seg[3] を作る。

seg: {0, 0, 0, 0}

ここで、右端が $3$ の区間 $[1,3]$ が出てくる。
この区間に $1$ が含まれるのは、最も右にある $1$ が $1,2,3$ のいずれかである場合である。
そのため、seg[1] から seg[3] に $10$ を加算する。

seg: {0, 10, 10, 10}

$i=4$ では、まずこれまでの最大値を使って seg[4] を作る。

seg: {0, 10, 10, 10, 10}

ここで、右端が $4$ の区間 $[2,4]$ が出てくる。
この区間に $1$ が含まれるのは、最も右にある $1$ が $2,3,4$ のいずれかである場合である。
そのため、seg[2] から seg[4] に $-10$ を加算する。

seg: {0, 10, 0, 0, 0}

$i=5$ では、まずこれまでの最大値を使って seg[5] を作る。

seg: {0, 10, 0, 0, 0, 10}

ここで、右端が $5$ の区間 $[3,5]$ が出てくる。
この区間に $1$ が含まれるのは、最も右にある $1$ が $3,4,5$ のいずれかである場合である。
そのため、seg[3] から seg[5] に $10$ を加算する。

seg: {0, 10, 0, 10, 10, 20}

最終的に、全体の最大値 $20$ が答えとなる。

答えは、int 型からはみ出る。
DP テーブルを含め、long long 型を用いること。

特になし。