Codeforces Round #619 (Div.2) E. Nanosoft

問題概要

$n \times m$ のマス目が与えられ、各マスは赤・緑・黄・青のいずれかに塗られている。

このマス目から $2k \times 2k$ の連続する正方形領域を取り出したときに、それが問題文の図の位置関係通りに4色の $k \times k$ の正方形で構成されているとき、これをレベル $k$ のNanosoftであると呼ぶことにする。

以下のクエリに $q$ 回答えよ。

左上のマスが $(r_{1}, c_{1})$ , 右下のマスが $(r_{2}, c_{2})$ である長方形領域に含まれる最大レベルのNanosoftの面積を求めよ。長方形領域がNanosoftを含まない場合は $0$ を出力せよ。

制約

$1 \le n, m \le 500$
$1 \le q \le 3\times 10^{5}$

解法

まず、Nanosoft判定をするために「ある正方形領域のマスが全て○色であるか」という判定を何度も行う必要がありそうです。これは色 $c$ ごとに「マス $(i, j)$ の色が $c$ ならば $A_{i, j, c} = 1$ 、そうでなければ $0$ 」という配列を用意して二次元累積和を取っておけばよいです。

$2k \times 2k$ の正方形領域について、ある代表点の位置を決めましょう。そして「代表点を $(i, j)$ とする $2k\times 2k$ の正方形領域は、レベル $k$ のNanosoftであるか？」という情報をクエリに備えて前計算しておくことを考えます。

このとき代表点を以下の位置に決めると、各代表点について単調性が成り立ちます。すなわち代表点 $(i, j)$ がレベル $k$ について条件を満たすならば、任意の $1 \le k^{\prime} \lt k$ に対してもレベル $k^{\prime}$ について必ず条件を満たします。

f:id:betrue12:20200215155409p:plain

このことから二分探索によって、各代表点が条件を満たす最大のレベル $k$ を求めることができます。これを単に代表点の最大レベルと呼ぶことにします。

それではクエリの処理方法を考えます。クエリで指定された長方形領域にレベル $k$ のNanosoftが含まれるならば、その一部としてレベルが $k$ より小さいNanosoftは常に含まれます。つまり単調性が成り立つので、「クエリで指定された長方形領域に、レベル $k$ のNanosoftが含まれているか？」という判定問題を用いた二分探索をしましょう。

クエリで指定された長方形領域に $2k \times 2k$ の正方形領域が収まっているときに、その正方形領域の代表点が存在する範囲を考えます。これは以下のように図示するとやはり長方形領域になることが分かります。

f:id:betrue12:20200215160523p:plain

この領域の中に最大レベルが $k$ 以上であるような代表点が存在すれば良いです。この判定は、長方形領域の最大値を効率的に求められるようなデータ構造に各代表点の最大レベルを入れておくことで処理できます。例えばセグメント木やスパーステーブルを二次元に拡張したものを用いることができます。

二次元セグメント木は構築 $O(nm)$ 、更新・取得クエリに $O(\log n\log m)$ かかります。二次元スパーステーブルは構築 $O(nm\log n\log m)$ 、取得クエリ $O(1)$ です。今回はクエリ数が多いので、二分探索を含めて各クエリに $\log$ を3つ付けるセグメント木だとギリギリです。スパーステーブルが良いでしょう。