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)

最も右にある $1$ の位置ごとに、その時点までに確定した区間から得られる最大得点を持つ。

位置 $0$ は、まだ $1$ を置いていない状態を表す。
最初はこの状態だけがあり、得点は $0$ である。

右端が $i$ の区間を考える前に、位置 $i$ を新しく最も右の $1$ にする状態を作る。

それ以前の $1$ の置き方は自由なので、この状態の得点は、それまでの状態の最大値になる。

その後、右端が $i$ の区間 $[l,i]$ を考える。
この区間に $1$ が含まれるのは、最も右にある $1$ の位置が $l$ 以上 $i$ 以下の場合である。

したがって、その範囲の状態全てに得点 $a$ を加える。
必要な操作は「全体の最大値」と「区間への一括加算」なので、lazy segment 木で高速に処理できる。

この入力例で実際に追う。

位置 $1$ を最も右の $1$ にする状態の得点は $0$ である。
右端 $1$ の区間はない。

右端の 1 の位置: 0  1
最大得点:          0  0

位置 $2$ についても同様である。

右端の 1 の位置: 0  1  2
最大得点:          0  0  0

位置 $3$ の状態を作った時点でも、最大得点は $0$ である。

ここで区間 $[1,3]$、得点 $10$ を考える。
最も右の $1$ が $1,2,3$ の場合は、この区間に $1$ が含まれる。
そのため、この3状態に $10$ を加える。

右端の 1 の位置: 0   1   2   3
最大得点:          0  10  10  10

位置 $4$ を最も右の $1$ にする場合、それまでの最大値 $10$ を引き継げる。

その後、区間 $[2,4]$、得点 $-10$ を考える。
最も右の $1$ が $2,3,4$ の状態に $-10$ を加える。

右端の 1 の位置: 0   1  2  3  4
最大得点:          0  10  0  0  0

位置 $5$ を最も右の $1$ にする場合も、それまでの最大値 $10$ を引き継げる。

区間 $[3,5]$、得点 $10$ により、最も右の $1$ が $3,4,5$ の状態に $10$ を加える。

右端の 1 の位置: 0   1  2   3   4   5
最大得点:          0  10  0  10  10  20

全状態の最大値は $20$ である。
したがって、答えは $20$。

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

特になし。