ABC477 F - Count Cells in a Window

考え方

グリッド面積がもう少し小さければ、二次元累積和で $O(MN+Q)$ で解ける。
これを、高速化と省メモリ化すればよい。

まず、クエリで必要となる累積和の値は、高々 $4Q$ ヶ所である。
よって、クエリ先読みをして、その場所の一覧を用意、ソートする。

これを上にあるものから $1$ 段ずつ、順に求めていく。
ある行の情報を考えるとき、前の行でのデータにその行の黒マス情報を加算する。
これは、結局のところ区間加算である。
つまり、遅延segment木でデータを持っておけば、$O(\log M)$ でその処理は完了する。
その遅延segment木で区間和を取れば、あるマスを基準にして左上にある黒マス個数が求まる。

それらを全て map か何かに入れておき、それを用いて二次元累積和の処理をすればよい。

計算量は、以下の4つの合計となる。

• 遅延segment木の構築に $O(M)$
• $N$ 行分の区間加算に $O(N\log M)$
• 高々 $4Q$ ヶ所の必要な累積和を求める処理に $O(Q\log M)$
• 必要な位置の一覧のソートと map の操作に $O(Q\log Q)$

よって、全体として $O(M+(N+Q)\log M+Q\log Q)$ である。

入力例1での動作

入力を受け取る。

n: 3
m: 6
q: 3

各行の黒マス区間:
[2, 4]
[1, 1]
[4, 6]

queries:
1 2 1 4
2 3 3 6
1 1 5 6

$S(i,j)$ を、上から $i$ 行、左から $j$ 列の範囲にある黒マスの個数とする。
各クエリ $(A,B,C,D)$ の答えは、二次元累積和と同様に $S(B,D)-S(A-1,D)-S(B,C-1)+S(A-1,C-1)$ で求められる。

したがって、この入力で必要な $S(i,j)$ だけを事前に列挙する。

上から順に行を追加していく。
各時点で、列ごとの「ここまでに黒マスだった回数」を遅延segment木で管理する。
必要な $j$ について、先頭から $j$ 列分の区間和を求める。

これで、各クエリに必要な累積和が揃う。

クエリ 1 2 1 4 の答えは $S(2,4)-S(0,4)-S(2,0)+S(0,0)=4$ となる。

クエリ 2 3 3 6 の答えは $S(3,6)-S(1,6)-S(3,2)+S(1,2)=7-3-2+1=3$ となる。

クエリ 1 1 5 6 の答えは $S(1,6)-S(0,6)-S(1,4)+S(0,4)=3-0-3+0=0$ となる。

したがって、出力は順に $4,3,0$ となる。

注意点

黒マスの個数は、int 型からはみ出る可能性がある。
long long 型を用いること。

別解

特になし。