Codeforces #223 Div1. B. Sereja and Tree

本番Cが先埋まっていたけど普通にこちらの方が簡単だし、終了後の練習で１発で通せた。
http://codeforces.com/contest/380/problem/B

問題

以下の手順で深さNの木を作る。

• 各頂点は(深さ, 深さ内の位置)で一意に特定できる。根は(1,1)である。
• 深さDの頂点群について、深さ内の位置が小さい順に子ノードを作る。その際深さ内の位置が2の累乗なら２個、そうでないなら１個子ノードを作る。

各頂点は数字の集合を保持する。
この木に対し、以下の２種類からなるM個のクエリを処理せよ。

• 深さd、位置l～rの頂点群に対し、数値xを集合に加える。
• 深さt、位置vの頂点に対し、そのサブツリー内に含まれる集合を合わせたものの要素数を答える。

解法

Mは数千とさほど大きくないので、２種類目のクエリに対しては、過去に行われた１種類目のクエリと総当たりでチェックし、(t,v)のサブツリーに(d,l)～(d,r)が含まれるか判定すればよい。

d=tなら、(t,v)に対応する深さdのサブクエリ中の頂点群を(d,a)～(d,b)とすると、[l,r]と[a,b]が交差すれば数値xが答えの集合に含まれる。

あとはvからa,bを求めればよい。
まず、子ノードの作り方は今の深さに関係なく深さ内の位置だけで決まるので、vから深さ(d-t)だけ下の頂点群を求めればよい。
vの子ノードの番号は、1～vのうち２の累乗の個数だけ増加するのでv+1+log(v)となる。
あとはこの操作をdoublingすることで深さLにおける番号をlogLで求めることができる。

上記doubling処理を事前にしておくと、(d,a)と(d,b)をlogNで求められる。
よって全体クエリではO(M^2 logN)で完了する。

int N,M;
int cnt[7010];
int up[200010][15];

int S;
int LV[10000],L[10000],R[10000],X[10000];


int num(int leflv, int pos) {
	int i;
	for(i=14;i>=0;i--) if(leflv&(1<<i)) {
		pos=up[pos][i];
		if(pos>=200000) break;
	}
	return pos;
}

void solve() {
	int f,i,j,k,x,y,l,r;
	
	for(i=1;i<=200000;i++) {
		int j=0;
		while(1<<(j+1) <= i) j++;
		up[i][0]=i+j+1;
	}
	FOR(x,14) {
		for(i=0;i<=200000;i++) {
			if(up[i][x]>=200000) up[i][x+1]=200001;
			else if(up[up[i][x]][x]>=200000) up[i][x+1]=200001;
			else up[i][x+1]=up[up[i][x]][x];
		}
	}
	
	cin>>N>>M;
	
	FOR(i,M) {
		cin>>x;
		if(x==1) {
			cin>>LV[S]>>L[S]>>R[S]>>X[S];
			S++;
		}
		else {
			cin>>l>>r;
			set<int> SS;
			FOR(j,S) {
				if(LV[j]<l) continue;
				int nr=num(LV[j]-l,r);
				int nl=num(LV[j]-l,r-1)+1;
				if(nl>R[j] || nr<L[j]) continue;
				SS.insert(X[j]);
			}
			cout << SS.size() << endl;
		}
	}
}

まとめ

ずいぶん珍しい形の木構造。
まぁその特性は使ってないけどね。doublingするので深さ依存のない構成法なら何でもいいし。