No.440

ある行についての区間 $[x, y)$ 内にある右向きのチワワ数を考える.

区間 $[x, y)$ 内の c, w, cw, ww, cww の個数をそれぞれ $c_{xy}, w_{xy}, cw_{xy}, ww_{xy}, cww_{xy}$ とする.

$c_{xy}, w_{xy}$ は累積和をあらかじめ計算しておけばいい.

$ww_{xy}$ は,

$$ww_{xy} = \frac{ w_{xy} * (w_{xy}-1) }{2}$$

である. また, $cw_{xy}$ は,

$$cw_{xy} = cw_{xn} - cw_{yn} - c_{xy}w_{yn}$$

となる. ただし, $cw_{in}$ はあらかじめ計算しておく.

このとき,

$$cww_{xy} = cww_{xn} - cww_{yn} - c_{xy}ww_{yn} - cw_{xy}w_{yn}$$

となる. ただし, $cww_{in}$ はあからじめ計算しておく.

これをすべての行/列および方向について計算する.