IOI 2008 Pyramid Base

揼了 200 行 code
應該是 IOI 有史以來 code length 最長的題目

其實咁複雜是因為 CASE 3 和 CASE 1, 2 的 approach 是不同的, 所以要分開兩段 code 去寫
做法分為 (1) Budget≠0 (2) Budget=0

對於(1), 可以 O(P * lg(P)* lg(Min(W, H)) 解決
對於(2), 可以 O(P * lg(P)) 解決

(1)
對答案做 binary search, 設 search length = d
想知有冇得 cover 一個 d * d 的 square 等同於將每一個 obstacle 向左和向下延伸d格, 然後睇下有冇一格個cost ≤ budget
用 segment tree 實現, 每個 node 記住 cover 和 best

(2)
對於 bugdet = 0, 即是要找全空的最大正方形
方法是, 用兩支指針指著 x1, x2, 每次 x1++ 就增加 x2 使得在 [x1, x2] 中最長的連續空白 ≥ (x2-x1+1)
也是要用 segment tree, 每個 node 記 cover, left max, right max, max

由於 W, H 可以去到 1,000,000, 所以一是離散 y 軸, 或者動態開樹
動態開樹應該比較易寫, 出錯的機會也較低