Codeforces #474 D. Full Binary Tree Queries

またレート上昇のチャンスをしょうもないミスで落とす…。
http://codeforces.com/contest/960/problem/D

問題

無限の大きさの二分木が与えられる。
根頂点には1のラベルが振られており、xのラベルの頂点には(2x)と(2x+1)のラベルを持った頂点が子頂点としてつながる。

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

• 頂点ラベル名Xが指定されるので、同じ深さの頂点をKだけローテートする。SubTreeは動かない。
• 頂点ラベル名Xが指定されるので、同じ深さの頂点をKだけローテートする。SubTreeもXとセットで動く。
• 頂点ラベル名Xが指定されるので、その頂点から根頂点までの経路上にある頂点のラベル名を列挙する。

解法

深さ毎にローテート量を保持すればよい。
Xは最大10^18なので、2つめや3つめのクエリも高々60個程度の高さまで考えればよい。

int N;
ll shift[63];
ll F[63],num[63],mask[63];
ll X,Y;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=0;i<=62;i++) {
		F[i]=num[i]=1LL<<i;
		mask[i]=num[i]-1;
	}
	
	cin>>N;
	while(N--) {
		cin>>i;
		if(i==1) {
			cin>>X>>Y;
			for(i=60;i>=0;i--) if(X>=F[i]) break;
			shift[i]+=(1LL<<61)+Y;
			shift[i]&=mask[i];
		}
		else if(i==2) {
			cin>>X>>Y;
			for(i=60;i>=0;i--) if(X>=F[i]) break;
			Y&=mask[i];
			for(j=i;j<=60;j++) {
				shift[j]+=(1LL<<61)+Y;
				shift[j]&=mask[j];
				Y<<=1;
			}
		}
		else if(i==3) {
			cin>>X;
			for(i=60;i>=0;i--) if(X>=F[i]) break;
			int level=i;
			X-=F[level];
			X+=shift[level];
			X=(X+(1LL<<61))&mask[level];
			while(level>=0) {
				cout<<(F[level]+((X+(1LL<<61)-shift[level])&mask[level]))<<" ";
				level--;
				X>>=1;
			}
			cout<<endl;
		}
	}
	
}

まとめ

これはすんなりだった。