きままにものづくり

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

POJ 2155 : Matrix

問題

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

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

解法

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

計算量

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

コード

広告を非表示にする