問題概要
$H\times W$ マス目のうち、 $N$ 点は黒です。各クエリではグリッドのマス $(X,A)$ が指定されるので、
- 指定されたマスから左右上方向に伸ばして得られる長方形であって、
- 黒マスを含まず、
- 縦横比が $T:S$ であるようなもの
の最大の大きさを求めてください。具体的には、最大で横 $SP$ 縦 $TP$ の長方形が作れる場合の $P$ の最大値を求めてください。
$N,Q \leq 2\times 10^5$ , $H,W\leq 10^9$
log 2 個の解法
クエリごとに大きさを二分探索します。
$P$ を固定すれば、
- 縦に $TP$ 以上取れる領域が、マス $(X,A)$ の周りに横 $SP$ にわたって存在するか？
を判定することになりますが、これは $(X,A)$ より上にある黒マスの高さの区間最小値のセグメント木を用いて二分探索することで判定できます。
このセグメント木を管理しながら平面走査することですべてのクエリにオフラインで答えられます。
計算量は $O(N\log N + Q\log ^2 N)$ です。
典型的な競プロの制限下では十分高速だと思います。
この log を 1 個削るための議論
一度、一般論に移ります。
$A$ , $B$ の値 ($1\leq A$ , $1\leq B$) が設定されていて、 $0\leq x\lt A$ , $0\leq y\lt B$ を満たす整数の組 $(x,y)$ 全体が探索空間であるとします。ここで、
- 点 $(x,y)$ は「 $x$ 優先」か「 $y$ 優先」のどちらか一方であるとします。ただし
- $(x,y)$ が $y$ 優先 $\implies$ $(x+1,y)$ が $y$ 優先
- $(x,y)$ が $x$ 優先 $\implies$ $(x,y+1)$ が $x$ 優先
- 点 $(x,y)$ は「有効」か「無効」のどちらか一方であるとします。ただし
- $(0,0)$ は有効
- $(x,y)$ が無効 $\implies$ $(x+1,y)$ と $(x,y+1)$ はどちらも無効
このとき次の条件を満たす点 $(x,y)$ がただ $1$ つ存在します。：
- $(x,y)$ は有効であり、次の $4$ つの条件を満たす：
- $(x,y)$ が $x$ 優先であれば、
- $x=A-1$ であるか $(x+1,y)$ が無効である。
- $(x,y)$ が $y$ 優先であれば、
- $y=B-1$ であるか $(x,y+1)$ が無効である。
- $y=0$ であるか $(x,y-1)$ が $y$ 優先である。
- $x=0$ であるか $(x-1,y)$ が $x$ 優先である。
- $(x,y)$ が $x$ 優先であれば、
このとき、本ブログで以前説明した方法により $O(\log N)$ ステップの探索で条件を満たす $(x,y)$ が得られます。（解説 ： AtCoder の問題の解説です。詳細はその投稿に任せます。）
log 1 個の解法
長方形の左端・右端の位置を決めれば、それに従って星を含まない領域の縦の長さの上限が決まります。左端・右端の位置としてありうるもの全体を探索対象とすれば、以下のようにして上に述べた枠組みに当てはめることができます。：
- 探索空間中の点 $(x,y)$ を、長方形の左端を右から $x$ 番目の星に、右端を左から $y$ 番目の星に揃えるという場合に対応させる。
- 左右いずれかに伸ばしたときに縦の長さの上限の減少が小さいほうを優先する方向とする。同点の場合は $x$ 優先とする。
- （長方形の端として、盤面の外周も考慮する）
- (縦の長さ)$/$(横の長さ)${}\leq T/S$ であるとき、「有効」であるとする。
これで横の長さをぎりぎりまで伸ばせるので、その状態と、その状態からさらに $1$ 回伸ばして縦のほうが長くなった状態を確認すれば十分です。
それぞれの二分探索はセグメント木上の二分探索とします。あらかじめセグメント木のノードをつなぎ合わせて二分探索木を作ることができるので、 $O(\log N)$ 時間です。平面走査も特に不都合は起こりません。
以上、全体の計算量は $O(N\log N + Q\log N)$ です。