人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

技術室奥プログラミングコンテスト #3:D - 巨大チェスボード

問題

beta.atcoder.jp

解法

偶数行・列の長さの累積和と奇数行・列の長さの累積和の2つを計算しておく.そうすれば,各クエリにおいて座標が (偶数,偶数) と (奇数,奇数) の黒マスの面積の合計が O(1) で計算でき,この2つを足し合わせれば黒マスの面積の合計は求まる.白マスの合計は,クエリで問われている範囲の全面積から黒マスの面積の合計を引けば求まる.前処理が一番重くて O(H + W).

解答

beta.atcoder.jp

一発 AC 出来てよかった.400 点問題にしては簡単だと思った.

f:id:babcs2035:20181028155727p:plain