1つの駒が守る領域は三角形のような形になります。もしこの領域が長方形であれば、imos法 を用いて問題に答えられることはよく知られています。実は今回の問題でも、斜め方向に差分/累積和を取ることで、imos法を用いて \(O(N^2+Q)\) で問題に答えることができます。

斜めの累積和の影響を考慮して、\(N\times 3N\) 程度の範囲を計算する必要があります。

実装例(C)

類題 Frog on Grid (yukicoder)