コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1622 (記事作成時点)
供養
解法
- 問題をある $X$ が与えられたときに、すべての $K \times K$ 区間の中央値が $X$ 以上であるかを判定する問題にする
- $S_{x, y}$ を $(1, 1)$ から $(x, y)$ の区間において $A_{i, j} \ge X$ である要素の個数とする
- $S_{x, y}$ は以下の式で求められる
\begin{align}
S_{x, y} = \begin{cases}
S_{x - 1, y} + S_{x, y - 1} - S_{x - 1, y - 1} + 1 & \mathrm{if}\; A_{i, j} \ge X \\
S_{x - 1, y} + S_{x, y - 1} - S_{x - 1, y - 1} & \mathrm{else}
\end{cases}
\end{align}
- $(x, y)$ を右下に置く $K \times K$ 区間における $X$ 以上の要素数 $Q_{x, y}$ は $Q_{x, y} = S_{x, y} - S_{x - K, y} - S_{x, y - K} + S_{x - K, y - K}$
- すべての $K \le x, y \le N$ について $Q_{x, y} \gt \lfloor \frac{K^{2}}{2} \rfloor$ ならば、すべての $K \times K$ 区間の中央値が $X$ 以上
- 上記の判定問題 $F(X)$ を $X$ について二部探索し、$F(X)$ が真となる下限値が答え
実装
計算量は $O(N^{2}\mathrm{log}(\mathrm{max}(A_{i, j})))$
公式解説
躓いた点
