JOI2013春合宿 day1 たのしい画像収集 (Collecting Images is Fun)

問題

日本語なので本文参照（http://imoz.jp/data/joi/2013-sp-d1-collecting.pdf）

制約条件

N≦20
Q≦2000000

方針

解説スライド（http://japl.pl/slides/joi/collecting_images_is_fun.pdf）の通り。
「白と黒が混在するマスの個数を数えればいい」ことに気づくかが全て。

あとは適当にsegment treeっぽく、上にたどって個数を更新する作業をやればいい。

ソースコード

int n, q;
int cntr[20], cntc[20];
vi r[21], c[21]; //0: white 1: black 2: mixed

inline void func(vi r[21], int *cntr, int b){
	r[n][b] ^= 1;
	b /= 2;
	for(int i = n - 1; i >= 0; i--, b /= 2){
		int prev = r[i][b];
		if(r[i + 1][b * 2] == r[i + 1][b * 2 + 1]) r[i][b] = r[i + 1][b * 2];
		else r[i][b] = 2;
		if(prev != r[i][b]){
			if(prev == 2) cntr[i]--;
			else cntr[i]++;
		}
	}
}

int main(){
	scanf("%d%d", &n, &q);
	
	rep(i, n + 1){
		r[i].resize(1 << i);
		c[i].resize(1 << i);
	}
	while(q--){
		int a, b;
		scanf("%d%d", &a, &b);
		b--;
		if(a == 0) func(r, cntr, b);
		else func(c, cntc, b);
		
		ll ans = 0;
		rep(i, n){
			ans += cntr[i] * (1ll << i) + cntc[i] * (1ll << i);
			ans -= (ll)cntr[i] * cntc[i];
		}
		printf("%lld\n", ans * 4 + 1);
	}
	return 0;
}