Posters (UVa Live Archive Asia - 2009 Ningbo)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=353&page=show_problem&problem=2759

問題

矩形の穴が空いた矩形のポスターをn枚窓に貼り付ける。ポスターは重なって貼ることもある。最終的にポスターが張られている面積はいくらになる？
0

解法

セグメントツリーを使う。セグメントツリーの各ノードには区間[l,r]と一致する場合はその区間が入ってる個数を記憶しておく。区間[l,r]の中でポスターに覆われている個数はそのノードが覆われている場合はr-l+1を返し、覆われてない場合は子ノードの合計になる。
あとはポスターを4分割して穴がない矩形にして左から順に見ていけば良い。