AtCoder EDPC W - Interval
全然わからなかったし、今もわかっていない（主に遅延セグ木）ので復習用に簡単にメモ
まず、方針からわからないけどググれば解りやすい解説がたくさん出てくる。
以下が解りやすかった。
Educational DP Contest : W - Intervals - kmjp's blog
上のリンクをはじめとして多くの解説ページの繰り返しになるけど、更新処理は単純 :
DPは要素数N+1、初期値0で初期化
dp(n) をnbit目が1、n+1bit以降は0となるような文字列の最大スコアと定義
更新は各nについて以下の3操作をする。
1. l=nであるような入力l,r,aそれぞれに対して、 dp(0..n-1) += a
2. dp(n) = max(dp(n-1))
3. r=nであるような入力l,r,aそれぞれに対して、dp(0..l-1) -= a
最終的な答えはmax(dp)、途中でn-1以下のdp(i)を区間加算とかでいじってるけど最終的には操作1と操作3で打ち消されるので結局操作2で代入された時点でのdp(n)に戻る。
1と3では区間加算、2では区間和と単値更新が必要、遅延セグ木は何もわからないのでググって貼った。（結局ここが一番難しかった）
非再帰版の遅延評価セグメント木の実装メモ - 日々ｄｒｄｒする人のメモ
セグ木を実装レベルで理解していないので大変に感じる。
上の実装を理解して自分で好きに弄れるようにならないとこういう問題の本番ACは厳しそう。
セグ木が他人のコードのコピペなので、自分で書いた部分が少なく恥ずかしいけど最終的なコード(1939ms)
