読者です 読者をやめる 読者になる 読者になる

プログラミング雑記:ABC017C

C++ Competitive Programming

・ABC017C+のいもす法(30+70+1)
 http://abc017.contest.atcoder.jp/submissions/349221
いもす法じゃない法(30+70)
 http://abc017.contest.atcoder.jp/submissions/349090
という感じで、単純な例では「一次元の重みつき部分区間の集合を扱う」ときに使う。
いもす法のポイントは何かといえば、
 - 区間の重みを開始点に足して終了点(の次の点)で引く
 - 始めから終わりまで累積を取っていく
の二つだけ。これで、各区間ごとの重さの合計値の最大と最小がわかる。区間のための配列を作るときは、長さを一つ大きくしておくことがコツかも(区間の最後+1では値は0になる)。