きままにものづくり

日々の気付いたことなんかを書いてます。

POJ 2155 : Matrix

PKU 蟻本

問題

N*N( $N \leq 1000$ )の配列が与えられる。各要素は、1か0しか値をとることができない。ふたつのクエリに対する処理を実行せよ。

(x,y)の要素が1なのか0なのか求めよ
(x1,y1,x2,y2)の範囲をフリップせよ

解法

二次元のBITを使い、範囲操作をするために4つの二次元BITを用意する。以前の問題(POJ3109)を二次元に拡張させる。境界条件は、一次元の場合とほとんど変わらないのでつまずかなかった。

計算量

$O( X \times T \times log N \times log N )$
N : 与えれる要素
T : クエリの数
X : テスト数

コード