AGC015 C - Nuske vs Phantom Thnook
N * M のグリッドに0または1が書いてあり、1をノード、1が隣同士になっているときにはエッジが張ってあるとみなすと、1の集合はTreeになる。領域(x[1,i],y[1,i], x[2, i], y[2,i])がQ個与えられるので、その領域でTreeの部分集合をとった時、領域内の連結成分の数を答えよ。
Treeの部分集合は一般に森(複数の木)になる。木は一般に「頂点数 - エッジ数 = 1」を満たすため、領域内の「頂点数 - エッジ数」がそのまま連結成分の数になる。エッジ数は各点ごとに上下左右を見ておき、その累積和を作っておく。また、領域の途中で切れた分を除くために、縦方向及び横方向での累積和も作っておく。また、頂点数は単に1の数で累積和を作っておく。すると領域が指定された時の「頂点数 - エッジ数」はO(1)で計算可能。全体ではO(N M)。
