問題 一直線にN個の島がN-1本の橋で繋がっている 島a[i]とb[i]を行き来できなくしてほしい、という形の要望M個を全て叶えるために取り除く必要のある橋の本数の最小値を求める 解法 クエリをa[i]の降順に見ていき、取り除いた橋の中で一番左の橋の番号rを保…

問題 H*Wの長方形をN*M個に区切り、そのうちいくつかの部分の面積を知っている 全体の面積を知りたいとき追加で必要な区間の面積の情報の最小値を求める 解法 Rx*Cx, Rx*Cy, Ry*Cx, Ry*Cyのうち3つの面積がわかれば残り1つの面積がわかる これを利用して盤面…