2155-Matrix

問題（外部リンク）

http://poj.org/problem?id=2155

実装の概要

A[x, y]が1か0かは、A[x, y]が何回長方形の内部に入ったかで判断することができます。
ただ、長方形内の全ての点を塗りつぶすように数え上げると間に合いません。
そこで、長方形の左上の座標に1、右上の更に1つ右に-1、左下の更に1つ下に-1、右下の更に1つ右下に1を加算します。
こうすることで（A[x,y]が長方形の内部に入った回数）=（A[1,1]からA[x,y]までの合計）となります。右下の更に右下に1を加算したのは、そうしないとそこの座標だけ2回長方形の外に出た扱いになってしまうからです。
加算の手間はで済むようになりましたが、クエリ数が多く表示の度にもかけるわけには行きません。
そこで、これらの処理を2次元のBITで管理することでA[1,1]からA[x,y]までの総和をで計算できるようになります。具体的なBITの実装は以下を参考にしてください。

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int t = Integer.parseInt(br.readLine());

		for(int i = 0; i < t; i++){
			String str = br.readLine();

			String tmpArray[] = str.split(" ");

			int n = Integer.parseInt(tmpArray[0]);
			int x = Integer.parseInt(tmpArray[1]);

			BIT2D bits = new BIT2D(n + 1, n + 1);

			for(int j = 0; j < x; j++){
				tmpArray = br.readLine().split(" ");

				if(tmpArray[0].equals("C")){
					int x1 = Integer.parseInt(tmpArray[1]) - 1;
					int y1 = Integer.parseInt(tmpArray[2]) - 1;
					int x2 = Integer.parseInt(tmpArray[3]) - 1;
					int y2 = Integer.parseInt(tmpArray[4]) - 1;

					//長方形の内部の始まり
					bits.add(y1, x1, 1);
					//長方形から外に出る
					bits.add(y1, x2 + 1, -1);
					bits.add(y2 + 1, x1, -1);
					//上記で2回引いてしまったので調整
					bits.add(y2 + 1, x2 + 1, 1);

				}
				else {
					int x1 = Integer.parseInt(tmpArray[1]) - 1;
					int y1 = Integer.parseInt(tmpArray[2]) - 1;

					//長方形の中に入った回数が奇数なら1、偶数なら0
					System.out.println(bits.sum(y1, x1)%2);
				}
			}

			//テストケース間に改行
			if(i != t - 1){
				System.out.println();
			}
		}
	}

}
class BIT2D {
	private int n;
	private int m;
	private BIT[] bits;

	BIT2D(int n, int m){
		this.n = n;
		this.m = m;
		bits = new BIT[n + 1];
		for(int i = 1 ; i <= n ; i++){
			bits[i] = new BIT(m);
		}
	}

	int sum(int i, int j) {
		int s = 0;

		i++;

		while(i > 0) {
			s += bits[i].sum(j);
			i -= i & (-i);
		}

		return s;
	}

	void add(int i, int j, int k){
		i++;
		while(i <= n){
			bits[i].add(j, k);
			i += i & (-i);
		}
	}
}

class BIT {
	private int n;
	private int[] bit;

	BIT(int n){
		this.n = n;
		bit = new int[n + 1];
	}

	int sum(int i) {
		int s = 0;

		i++;
		while(i > 0) {
			s += bit[i];
			i -= i & (-i);
		}

		return s;
	}

	void add(int i, int k){
		i++;
		while(i <= n){
			bit[i] += k;
			i += i & (-i);
		}
	}
}