ABC203 D Pond
最小値の最大化・最大値の最小化は二分探索という典型がある. 今回は中央値の最小化であるが, 同様にして二分探索を用いて解くことができる. 具体的には, $ C(x) := 中央値の最小値を$ x以下にできるか? という判定問題を解くことを考える. 中央値の定義が, $ \lfloor \frac{K^2}{2} \rfloor + 1番目に高いマス であることに注意すると, この条件は「AtCoder公園の敷地内に完全に含まれる$ K \cdot Kの区画であって, $ x以下の高さが$ K^2 - (\lfloor \frac{K^2}{2} \rfloor + 1) + 1 = K^2 - \lfloor \frac{K^2}{2} \rfloor個あるようなものが存在する」として言い換えられる. よってある$ xが定まったときに, すべての区画について$ x以下の数の個数が高速に求められればよい. これは各マスについて$ xより高いなら$ 0, $ x以下なら$ 1とした二次元配列を持ち, その累積和を前計算しておくことにより高速に求められる. よってこの問題を$ A_{max} = 10^9として$ O(N^2 \log A_{max})で解くことができた.