ABC260 G - Scalene Triangle Area (600)
全てのクエリを愚直に解くには$ \mathcal{O}(QNM)かかる
各行毎に駒の数の累積和を求めておく
条件を考察するとそのマスを守れる範囲は、
同じ行は左の$ 2mマス
その上は$ 2m-2マス
という風に上に$ m行だけになる
各クエリにおいて
上のm行について範囲内にいるコマを累積和で行毎に求める
$ \mathcal{O}(QM)でC++では間に合う
解説では斜めの累積和で計算量が更に低い
問題: https://atcoder.jp/contests/abc260/tasks/abc260_g
提出: https://atcoder.jp/contests/abc260/submissions/33316512
#ABC260 #600pt #G #ABC #AtCoder
#累積和 #斜め累積和