Codeforces #368 Div2 D. Persistent Bookcase

良くわからん問題。
http://codeforces.com/contest/707/problem/D

問題

01の２値を取る二次元配列B[i][j]を考える。
初期状態はBはゼロである。

以下のクエリを順次処理し、1の値の個数を処理せよ。

• B[i][j]を1にする。
• B[i][j]を0にする。
• B[i][*]をすべて01反転する。
• i番目のクエリ実行後の状態に戻す。

解法

まずは4番目のクエリを考える。
各クエリはどのクエリ実行後の状態の後に行うかを考えると、根付き木になっていることになる。
そこで、クエリは一見上から順に一方向になっているように見えるが、DFSで行ったり戻ったりしながら各クエリを処理すればよい。

各クエリ、実行前の状態を覚えておけば、実行後にそこに依存するクエリを全部DFSした後、実行前の状態に戻して呼び出し元に戻ることができる。

int H,W,Q;
bitset<1024> B[1024], rev;
int R[101010];
int A[101010],I[101010],J[101010];
vector<int> E[101010];

void dfs(int cur,int now) {
	int add=0,del=0,i;
	
	if(A[cur]==1 && B[I[cur]][J[cur]]==0) add++, B[I[cur]][J[cur]]=1, now++;
	if(A[cur]==2 && B[I[cur]][J[cur]]==1) del++, B[I[cur]][J[cur]]=0, now--;
	if(A[cur]==3) {
		now -= B[I[cur]].count();
		B[I[cur]] ^= rev;
		now += B[I[cur]].count();
	}
	
	R[cur]=now;
	FORR(r,E[cur]) dfs(r,now);
	if(A[cur+1]>=1 && A[cur+1]<=3) dfs(cur+1,now);
	
	if(A[cur]==3) {
		now -= B[I[cur]].count();
		B[I[cur]] ^= rev;
		now += B[I[cur]].count();
	}
	if(add) B[I[cur]][J[cur]]=0, now--;
	if(del) B[I[cur]][J[cur]]=1, now++;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>Q;
	FOR(i,W) rev[i+1]=1;
	FOR(i,Q) {
		cin>>A[i+1]>>I[i+1];
		if(A[i+1]==4) E[I[i+1]].push_back(i+1);
		if(A[i+1]==1 || A[i+1]==2) cin>>J[i+1];
	}
	dfs(0,0);
	
	FOR(i,Q) cout<<R[i+1]<<endl;
}

問題

一見有向辺の根付き木に見えて、両方向に移動することが容易なのがミソなのかな。