Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Educational DP-W Intervals】遅延セグツリーを使って最善値を管理する

W - Intervals

問題

長さNの01文字列と区間(l,r,a)について、文字列がこの区間の中に1が一つでも立っている場合スコアaを加算することにする。このような区間がM個ある場合に、最大スコアを求めよ。

方針

区間を右端について昇順で見ていく。今、rまでみた時の最大値がdp(r)と書けるとする。この最大値をとる01列のうちもっとも右の1が存在し、それより右は全部0という形になっている。

あとでまとめるが、整理のためにひとまず分類する。

r+1を見た時、新しい区間がそのもっとも右の1に

  1. 重ならない場合:dp(r+1)は、dp(r)か、dp(r)+aである。
  2. 重なる場合:dp(r+1)は、dp(l)か、この区間を過去のdp(l+1..r)にa加算して補正した値とdp(r)+aの大きい方である。(新しい区間を採用しない場合と、する場合)

f:id:akiradeveloper529:20191002210818j:plain

これはまとめて、

  1. dp(r)をdp(r+1)に代入する
  2. 新しい区間を加算する
  3. dp(r+1)を最大値クエリで求める

という処理になる。なぜならば、新しい区間の左端までのdp(l)と、それ以降加算した場合の最大値を求めるという処理に統一出来るからである。

これは、遅延セグツリーを使うと実現出来る。

実装

fn solve() {
    input!{
        N:usize,M:usize,
        lra:[(usize,usize,i64);M]
    }
    let mut prev = vec![vec![]; N+1];
    for (l,r,a) in lra { 
        prev[r].push((l,a));
    }
    let mut seg: SEG<MAX_RAQ> = SEG::new(0, N+1);
    for r in 1..N+1 {
        // rより前のマックス
        let curmax = seg.query(0, r);
        // キャリーオーバー
        seg.update(r, r+1, curmax);
        for &(l,a) in &prev[r] {
            seg.update(l,r+1,a);
        }
    }
    let res = seg.query(1,N+1);
    let ans = if res < 0 { 0 } else { res };
    println!("{}", ans);
}