AOJ 1337 Count the Regions

いもす法を排他的論理和でやるみたいな方法で解きました。
長方形に番号をふります。
グリッドのマスの、2進数のある桁が1になっているとき、そのマスには(その桁数)番の長方形が存在する、という風に対応させます。
いもす法みたいに配置して累積XORをとるとうまくできます。
累積XORを使うとbit分の長方形を同時に扱うことができるので、定数倍高速化されます。うれしい

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define IDX(x,v) distance(v,lower_bound(v,(v)+2*N,x))
#define fs first
#define sn second
typedef long long ll;
typedef pair<int, int> P;
typedef pair<P, P> R;
int N;
R rec[50];
int X[100], Y[100];
ll a[103][103];
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
void dfs(ll b, int y, int x){
	a[y][x] = -1;
	for(int i=0; i<4; i++){
		int ny = y+dy[i];
		int nx = x+dx[i];
		if(0<=ny&&ny<=2*N+1 && 0<=nx&&nx<=2*N+1 && a[ny][nx]==b)
			dfs(b,ny,nx);
	}
}
int main(){
	while(scanf("%d",&N) && N!=0){
		memset(a,0,sizeof(ll)*103*103);
		for(int i = 0; i < N; i++){
			int l, t, r, b;
			scanf("%d %d %d %d",&l,&t,&r,&b);
			X[2*i]=l; X[2*i+1]=r;
			Y[2*i]=t; Y[2*i+1]=b;
			rec[i] = R(P(l,t),P(r,b));
		}
		sort(X,X+2*N);
		sort(Y,Y+2*N);
		for(int i = 0; i < N; i++){
			int l = IDX(rec[i].fs.fs,X);
			int t = IDX(rec[i].fs.sn,Y);
			int r = IDX(rec[i].sn.fs,X);
			int b = IDX(rec[i].sn.sn,Y);
			a[t+1][l+1] += (1L)<<i;
			a[t+1][r+1] += (1L)<<i;
			a[b+1][l+1] += (1L)<<i;
			a[b+1][r+1] += (1L)<<i;
		}
		for(int i = 1; i <= 2*N+1; i++)
			for(int j = 1; j <= 2*N+1; j++)
				a[i][j] = a[i][j-1]^a[i][j];
		for(int j = 1; j <= 2*N+1; j++)
			for(int i = 1; i <= 2*N+1; i++)
				a[i][j] = a[i-1][j]^a[i][j];
		int ans = 0;
		for(int i = 0; i<=2*N+1; i++){
			for(int j = 0; j<=2*N+1; j++){
				if(a[i][j] >= 0){
					dfs(a[i][j],i,j);
					ans++;
				}
			}
		}
		printf("%d\n", ans);
	}
}