2007JOI春合宿Day1-3 Mall 解説

問題リンク

解説

二次元累積和というテクニックを使います。

二次元累積和については、けんちょんさんの記事を参照してください。

二次元累積和を使うと、「ある長方形領域に人が住んでいるか」と、「住んでいない場合、買収にかかるコストはいくらか」を で求められます。 よって、この問題を で解くことができます。

二次元累積和は、情報オリンピックに限らず競技プログラミング全体で頻出のテクニックです。 スムースに予選を突破するためにも、押さえておきましょう。