Codeforces Round #371 (Div. 1) D. Animal and Puzzle
http://codeforces.com/contest/713/problem/D
問題概要
(x1,y1)から(x2,y2)の長方形領域内にある最大正方形を求めるというクエリを順次処理せよ。
解法
最大正方形はdp[i][j] := 右下が(i,j)である最大の正方形のサイズとして計算できる。
「サイズ x の正方形が存在するかどうか」を二分探索できることに気づけば簡単。
下図の緑色の領域外を右下とするサイズ x 以上の正方形は作れないので、緑色の領域内の dp[i][j] の最大値が x 以上であれば OK。
2D sparse table を書いておけば構築 O(nm logn logm)、クエリ O(t log min(n,m)) でできるしこれで通る。1964ms, 203536KB（何か実行する度に数百ms オーダーで実行時間が変わる…）。
2D sparse table は sparse table とほぼ同じ原理なので実際にコードを見た方が分かると思う。
segtree に sparse table RMQ を持たせればメモリが節約できる。2480ms, 47916KB。メモリを節約すれば速くなるかなと思ったけどそうでもなかった。
2D sparse table 自体は cheflong で書いたことがあったので、単純に二分探索に気づかなかった。
