https://atcoder.jp/contests/dp/submissions/12909348
in-place DPというやつらしい。
- メイン条件 + index条件 → セグメントツリーにバラバラに入れる + RMQ (Range Max Query)
逆の逆の操作は同値「背が高い∧indexが減少」を抜く⇔「背が低い∧indexが増加」を増やすと言い換える。前者より後者のほうが実装が楽になるため、後者の方法を考える。
背が低い順にというメイン条件があるため、まず背の順でソートする。ソートした花を昇順に見ていき「背が低い∧indexが増加」の答え(美しさ合計)をdpとするとdp[i] = a[i] + max( dp[0, i) )となる。dpが再帰的に定義されるので、dp[i]もmax( dp[0, i) )も「背が低い∧indexが増加」を満たす。普通のvectorではmax( dp[0, i) )の処理に かかってしまうが、セグメントツリーにバラバラに入れていく実装で
で処理できるようになる。セグメントツリーには点加算と区間最大値取得を実装する。
