AtCoder ARC #049 : D - すわっぷしまーす

実装は意外にシンプル。
http://arc049.contest.atcoder.jp/tasks/arc049_d

問題

N段の完全二分木を考える。
葉以外の(2^N)-1頂点には、根から順に1,2,3...((2^N)-1)の位置が割り振られている。
また、葉の(2^N)頂点には左から順に1,2,...,(2^N)の番号が割り振られている。

ここでswap(x)という処理を定義する。
これは位置xの頂点について、左側の部分木と右側の部分木の葉の要素を入れ替える処理である。
(番号は入れ替わるが、位置は入れ替わらない点に注意すること)

以下のクエリQ個を順次処理せよ。

• 左からa番目の葉に書かれている番号を答えよ。
• 2値(a,b)が与えられる。swap(a),swap(a+1),...,swap(b)を順に処理せよ。

解法

Editorialを見て回答。
Editorialでは木の高さについて言及しているが、こちらは深さを用いているので注意。

SegTreeの要領で、各位置に対し「以下の部分木において、深さdの位置が左右反転しているかどうか？」をbitmaskで管理する。
後者のクエリについては、swap群を同じ深さ同士のswap群に分割しよう。
また、同一の深さのswap群について、SegTreeの要領でswapをまとめ上げる。
例えば、深さdの頂点群(4k～4k+3)に対しswap(4k),swap(4k+1),swap(4k+2),swap(4k+3)が行われるならば、頂点kのbitmaskに「深さdでswapする」と書いておけばよい。

前者のクエリでは、a番の葉に到達するよう二分木を上から順番にたどっていくが、経由した頂点においてbitmaskで各深さで左右反転をするよう指示されている場合、左右反対の頂点に順次たどるようにして到達した葉の「位置」（番号ではない）を答えればよい。
後者のクエリについても、これまでの左右反転クエリの影響を受け適用範囲も左右反転することに注意。
サンプルケースの範囲では、クエリ自体の左右反転の影響を無視しても通るが、システムテストは通らない。

int N,Q;
int dswap[1<<20];

void dfs(int ML,int MR,int L,int R,int d,int cur,int mask,int lv) {
	if(R<=ML || L>=MR) return;
	if(L<=ML && R>=MR) {
		dswap[cur] ^= 1<<d;
	}
	else {
		mask ^= dswap[cur];
		int p=(mask>>lv)&1;
		
		dfs(ML,(MR+ML)/2,L,R,d,cur*2+p,mask,lv+1);
		dfs((MR+ML)/2,MR,L,R,d,cur*2+p^1,mask,lv+1);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	
	while(Q--) {
		cin>>i>>x>>y;
		if(i==1) {
			x--;
			y=1;
			int mask=0;
			for(i=0;i<N;i++) {
				mask^=dswap[y];
				y=y*2 + (((mask>>i)^(x>>(N-1-i)))&1);
			}
			_P("%d\n",y-(1<<N)+1);
		}
		else {
			y++;
			for(i=0;i<N;i++) {
				int L=1<<i,R=L*2;
				L=max(L,x);
				R=min(R,y);
				if(L>R) continue;
				dfs(1<<i,2<<i,L,R,i,1,0,0);
			}
		}
	}
}

まとめ

とはいえ本番中にこれは思いついてなさそう。