はじめに

2か月前に始めた「教育的dp問題」も終わりに近づいてるけど、最も難しいと噂の問題「Intervals」とご対面しました。
考えてみても分からなかったので、解説に従って解こうと思う。

問題

0と1のみからなる文字数Nの文字列Sを作って、それによる最高得点を求める問題。
M個のクエリが与えられ、その内容は以下のとおり。
- (l r a)の三つの数値が与えられる。Sのl〜r文字目の間に1が含まれれば、点数aが与えられる。
入力例

5 3 // 5文字、3クエリ
1 3 10 // クエリ① 1〜3文字目に1があれば、10点
2 4 -10
3 5 10

この場合の解答は20です。
具体的には、S="10001"で、スコアがクエリ①+クエリ③=10+10=20 となります。

dpの書き方（解説より）

二次元のdp[i][j]を考えます。dpは最高点を格納します。
- i：Sのi文字目までが確定した状態。つまり、Sの0..<iの値が決まった状態。
- j：1がある最後のインデックス。だから、d[4][2]は、S=[1 1 1 0],[1 0 1 0],[0 1 1 0],[0 0 0 1]の組み合わせの中での最高点になるね。当然、j<iだよ。
- なお、実行済みのクエリは、0-idxに変換後でr<iとなる(l r a)のみとします。つまり、r<iとなるクエリを対象としたとき、dp[i].max()!が正解となるね。当然、最終回答は、dp[N].max()!となる。

コード化する（高速化前）

とりあえずは、上記dpを用いて、入力例を解くことだけを目的に自力でコード化する。

extension Array { // 二次元配列の省略記法用
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var A:[(Int,Int,Int)] = []
for _ in 0..<M {
let (a,b,c) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2])}[0]   
    A.append((a-1,b-1,c)) // 範囲は0-idxに
}

// クエリ配列Aのうち、範囲(l,r)が(l,i-1)となっているものを選び、
// l<=jならばaをスコアに加算し、スコア合計を返す関数
func score(_ i:Int,_ j:Int)->Int{
    var sum = 0
    for (l,r,a) in A {
        if i-1 == r {
            if l <= j { sum += a }
        }
    }
    return sum
}

var dp = [[Int]](N+1,N,0) // 省略記法
// print(0,dp[0]) // 経過確認用print文

for i in 1...N{

    // パターン⓪　作成途中のSの右端が0のとき（dp[i][i-1]以外)
        for j in 0..<(i-1){
            dp[i][j] = dp[i-1][j] + score(i,j)
        }

    // パターン①　作成途中のSの右端が1のとき（dp[i][i-1]のとき）
        var temp = 0
        for j in 0..<(i-1){
            temp = max(temp,dp[i-1][j])
        }
        dp[i][i-1] = temp + score(i,i-1)

    // print(i,dp[i]) // 経過確認用print文
    
}

print(dp[N].max()!)

コレで、Nが小さいときは解けます。
まぁ、dpの書き方さえヒントを貰えれば、ここまでは書けるよね。
でも、計算量を考えると･･･
- パターン⓪のforループにscore関数が含まれていて、score関数もforループ(計算量O(M))を含むから、結局、$O(N^2･M)$になるね。
- おや？複数有る解説の一つを見ると、高速化前でO((N+M)･N)になるみたいなことが書いてあったけど...ま、まぁ、気にしない。どうせ、高速化するんだし。

理解のためにdpを見る

まず、下記入力を前提とします。

5 3 // 5文字、3クエリ
1 3 10 // クエリ㋐ S[0..<3]に1が有れば、10点
2 4 -10 // クエリ㋑ S[1..<4]に1が有れば、-10点
3 5 10 // クエリ㋒ S[2..<5]に1が有れば、10点

上記入力に対し、i毎のdp[i]は以下のとおり

0 [0, 0, 0, 0, 0]
1 [0, 0, 0, 0, 0]
2 [0, 0, 0, 0, 0]
3 [10, 10, 10, 0, 0]
4 [10, 0, 0, 0, 0]
5 [10, 0, 10, 10, 20]

各iでの動作を考える。
- i=0 何の操作もないため、初期化のまま全部0。
- i=1,2 該当クエリが無いので、dp[i]に変化なし
- i=3 クエリ㋐がヒット（score関数が動作）
  - パターン⓪により、j=0,1で「+10」
  - パターン①により、j=2で、max(0,0)に「+10」
- i=4 クエリ㋑がヒット
  - パターン⓪により、j=1,2で「-10」
  - パターン①により、j=3で、max(10,10,10)に「-10」
- i=5 クエリ㋒がヒット
  - パターン⓪により、j=2,3で「+10」
  - パターン①により、j=4で、max(10,0,0,0)に「+10」
よし、理解した！

高速化の準備

制約は、$N,M≦10^5$なので、目指すはO(N･logN)かO(N･logM)かO(N･log(N+M))なんだろうな。一番外のforループでNを使うことは確定だから、残りをlogで収めないと駄目。
高速化前のパターン⓪①を見ると、dpは、dp[i][j]とdp[i-1][j]の形しかないね。これはdpのin-place化が使えるパターンだね。
じゃあ、検討してみよう。一次元配列dp[j]にin-place化した前提で考えるよ。
- パターン①のtemp計算は、dp[j]をセグ木に食わせれば、maxクエリでlogNで計算できるね。
- パターン⓪①のscore関数については、毎回forループを回してO(M)の計算量を使っているけど、大外のfor-iループに連動させて、必要なクエリだけ使えば良いんだから、クエリ全体のforループを回さない形にすれば良いね。
- 分かったかも！予め、Aの要素(l,r,a)のr順で並べておけば良いのでは？
まずは、in-place化（dp[i][j] ⇒　dp[j]）してみます。
- in-place化によりi-1でのdpを最初に使いたいのは、パターン①の方なので、パターン①の後にパターン⓪を処理する順序にするよ。dp設定より前は変更無いよ。

///前半省略///

var dp = [Int](N,0) // in-place化！
for i in 1...N{

    // パターン①　作成途中のSの右端が1のとき（dp[i-1]のとき）
        var temp = 0
        for j in 0..<(i-1){
            temp = max(temp,dp[j])
        }
        dp[i-1] = temp + score(i,i-1)
        
    // パターン⓪　作成途中のSの右端が0のとき（dp[i-1]以外)
        for j in 0..<(i-1){
            dp[j] = dp[j] + score(i,j)
        }
}
print(dp.max()!)

-　上記のパターン①②を少し書き換えると以下のとおり、スッキリ！
-　スッキリした後の見た目から、遅延セグ木を1つ作れば対処できる方針が思い浮かぶね。

        var temp = 0
        for j in 0..<(i-1){
            temp = max(temp,dp[j]) // セグ木のmaxクエリで対処できる！
        }
        // dp[i-1] = temp + score(i,i-1)
        dp[i-1] = temp

        // for j in 0..<(i-1){
        for j in 0..<i{
            dp[j] = dp[j] + score(i,j) // 遅延セグ木の区間変更クエリ（加算クエリ）で対処できる！
        }

遅延セグ木（区間変更クエリ：加算、区間取得クエリ：最大値）

詳しくは、遅延セグ木の投稿を見てね。
下記はこの遅延セグ木を利用したコード。

import Foundation // 遅延セグ木のprtTree等で必要
class LazySegTree {・・・} // 遅延セグ木
extension Array {・・・} // 二次元配列の省略記法用

let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var A:[(l:Int,r:Int,a:Int)] = []
for _ in 0..<M {
let (a,b,c) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2])}[0]   
    A.append((a-1,b-1,c))
}

A.sort{$0.1 > $1.1} // スタック的に、配列のお尻から先に取り出すため、rの降順で並び替えた。0(MlogM)

var dp = LazySegTree(N)

for i in 1...N{

    // 最大値クエリ（区間取得）
    if i > 1 {
        let mx = dp.query(0,i-1)
        dp.update(i-1,mx)
    }

    // 加算クエリ（区間変更）
    while !A.isEmpty && A.last!.r == i-1  {
        let (a,b,x) = A.removeLast()
        dp.add(a,b+1,x)
    }

}

print(max(0 , dp.query(0,N))) // Sの0/1を全て0にすれば負にならないため
                              //「max(0,」で0以上を保証

この問題の難しいところは、遅延セグ木を作ることであり、遅延セグ木さえ用意できれば大したことないね。
上記を提出すると、1000ms程度でACだったよ！やった！

おわりに

凄く疲れました。なんだか、とても眠いんだ...
遅延セグ木の一般化のコードがちょっと汚いけど、しばらく放置かな。
in-place化は分かってきた気がする。遅延セグ木を使った問題もいくつかやっつけたいね。
「教育的dp問題」も、あと少しだ...気力で頑張る！