最大長方形 与えられた条件を満たす最大の長方形の面積を求める傾向の問題 最大正方形はO(HW), ヒストグラムの中の最大長方形O(N), 最大長方形O(HW) 最大正方形 : dp解法がある ヒストグラムの中の最大長方形 : stackを使った解法がある 最大長方形 : 「ヒストグラムの中の最大長方形」の問題に帰着させることができる 問題 AOJ 最大正方形 解説 AOJ ヒストグラムの中の最大長方形 解説 AOJ 最大長方形 解説 (関係無いかも知れないが)部分長方形問題まとめ ECR30 Forbidden Indices Meldable Heap Meld(併合,マージ)ができるヒープ マージテクで実装するとMeldはO(log^2N) Skew Heapで実装するとMeldはO(logN) 問題 AOJ JAG春コンテスト2013 E. Minimum Spanning Tree