kojingharangの日記

Codeforces #223 Div2 D. Sereja and Tree

23:18 |

• 深さlevel、左からpos番目のノードに対して posが2の累乗なら左右の子、それ以外なら右の子を持つ最大深さNの木がある。各ノードには空集合が入っている。
• 以下の２つの命令が計M個くるので処理する問題。
• (1) level[i], posL[i]〜posR[i] のノードに入ってる集合に x[i] を追加する
• (2) level[i], pos[i] のノードとそのsubtreeの集合の和集合の要素数を印字する
• 1≦N,M≦7000
• 1≦x[i]≦10^6

• ややこしや
• もう寝ようかな
• ややこしや

• 図が完全二分木じゃないのは間違ってる？
• よく読んだら２つの子を持つのは2の累乗のときだけ, か...
• なのでノード数は 2^7000 とかにはならない。深さ7000の葉の個数は109332個

• (1) が来た時
• data[i][level][3] = {L, R, X} ... i番目の追加命令では深さlevelに対して L≦pos≦R に X を追加した
• と覚えておけば (2) のとき O(MlogM) で答えが出せるからそうしよう
• →256MB に入らない

• おしまい

• あとで

• 逆に(2)が来た時に全深さに対して pos の範囲を計算しといて追加命令の範囲と共通箇所があればカウント
• だとメモリが少なくて済む
• なるほど
• accepted in practice

int chL[110000]; // L child, 1base
int chR[110000]; // R child, 1base
int rL[7007];
int rR[7007];
int T[7007];
int L[7007];
int R[7007];
int X[7007];

// 109332
int main() {
	ios::sync_with_stdio(false);
	ll N,M;
	ll type,t,v;
	while(cin>>N>>M) {
		int cs=1;
		REP(i, 110000) {
			int ch = (POPCOUNT(i+1)==1) ? 2:1;
			chL[i+1]=ch==2?cs++:-1;
			chR[i+1]=cs++;
		}
		int hints=0;
		REP(i, M) {
			cin>>type;
			if(type==1) {
				cin>>T[hints]>>L[hints]>>R[hints]>>X[hints];
				hints++;
			} else {
				cin>>t>>v;
				REP(j, t) rL[j]=rR[j]=-1;
				rL[t]=rR[t]=v;
				RANGE(j, t, N) {
					rL[j+1]=chL[rL[j]]==-1 ? chR[rL[j]] : chL[rL[j]];
					rR[j+1]=chR[rR[j]];
				}
				map<int, int> ma;
				REP(hi, hints) {
					if(rL[T[hi]]==-1) continue;
					bool in = !(R[hi]<rL[T[hi]] || rR[T[hi]]<L[hi]);
					if(in) ma[X[hi]]=1;
				}
				cout<<ma.size()<<endl;
			}
		}
	}
	
	return 0;
}

ツイートする