3/16 PKU

2843 Cutting Cake

正方形のケーキを切り出す。ケーキを切るときには、決められた座標の長方形を切り出すように切る。すでに切り出されてても構わず切り出す。ケーキを切ったときに、切った部分がいくつかに分かれているかもしれない。何個のつながりに分かれているかを各切断に対して求めよ。

平面走査×Segment Treeでケーキの各マスがどの切断によって切りだされるかを求め、その後BFSで連結部分の数を求める。DFSだとREになるみたい