区間和(更新無し)の最大値(abc183_d)

概要

区間和(更新無し)の最大値を求める方法を、図で解説する。
※加算、減算を同時に行える。

問題

https://atcoder.jp/contests/abc183/tasks/abc183_d

解説図

以下の様な区間の最大値を求める。

1.全探索(ダメなパターン)

処理量がO(nw)
→(問題の制約的に)最大で20万×20万・・・とても間に合わない。

2.累積和を使う

「要素が変わるタイミング」は以下の通り。

これを1つの配列(変動表)にまとめて・・

累積和を求める。

→最大値は「7」と分かる。
この方法なら処理量はO(n+w)。最大で20万+20万なので、問題なく回答できる。