AtCoder ABC #417 : G - Binary Cat

これは解けても良かったな…。
https://atcoder.jp/contests/abc417/tasks/abc417_g

問題

S[0]="0";
S[1]="1"
とする。以降を整数列L,Rを用いて以下のように定義する。
S[i]=S[L[i]]+S[R[i]]
なお、L[i]とR[i]はi未満である。

S[i]に対し整数X[i]が与えられる。
S[i]のX[i]文字目を答えよ。

解法

各文字列に対し、クエリの集合を以下の形で持つ。
(文字位置,クエリ番号)
なお、この集合は文字位置でソートしておき、大きい順or小さい順に値を取れるようにしておく。
また、集合内の文字位置を一斉に減算できるよう、集合全体に対し文字位置の減算量を保持しておく。

文字列の番号の大きい順に、クエリを再帰的に「S[i]のx文字目であれば、S[L[i]]のx文字目またはS[R[i]]のx-|S[L[i]]|文字目である」としてより手前の文字列のクエリに置き換えていこう。
ただし毎回これを愚直に行うとO(Q^2)かかる。
そこで、マージテクの逆の要領で処理する。
クエリをL[i]またはR[i]のクエリ集合に振り分ける際、|S[L[i]]|と|S[R[i]]|の小さい方に対しては、クエリの中身を1個1個移動するが、それ以外はマージテクの要領でクエリ集合全体を振り分けていく。

int Q;
int L[505050],R[505050];
ll X[505050];
ll len[505050];
ll dif[505050];
set<pair<ll,int>> S[505050];
int ret[505050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	len[0]=len[1]=1;
	FOR(i,Q) {
		cin>>L[i+2]>>R[i+2]>>X[i+2];
		len[i+2]=min(len[L[i+2]]+len[R[i+2]],1LL<<60);
		S[i+2].insert({X[i+2],i});
	}
	
	for(i=Q+1;i>=2;i--) {
		if(len[L[i]]>len[i]-len[L[i]]) {
			while(S[i].size()&&S[i].rbegin()->first-dif[i]>len[L[i]]) {
				auto p=*S[i].rbegin();
				S[i].erase(--S[i].end());
				S[R[i]].insert({p.first-dif[i]-len[L[i]]+dif[R[i]],p.second});
			}
			if(S[L[i]].size()<S[i].size()) {
				swap(S[i],S[L[i]]);
				swap(dif[i],dif[L[i]]);
			}
			FORR2(l,j,S[i]) S[L[i]].insert({l-dif[i]+dif[L[i]],j});
			
		}
		else {
			while(S[i].size()&&S[i].begin()->first-dif[i]<=len[L[i]]) {
				auto p=*S[i].begin();
				S[i].erase(S[i].begin());
				S[L[i]].insert({p.first-dif[i]+dif[L[i]],p.second});
			}
			dif[i]+=len[L[i]];
			if(S[R[i]].size()<S[i].size()) {
				swap(S[i],S[R[i]]);
				swap(dif[i],dif[R[i]]);
			}
			FORR2(l,j,S[i]) S[R[i]].insert({l-dif[i]+dif[R[i]],j});
		}
	}
	FOR(i,2) FORR2(a,b,S[i]) ret[b]=i;
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

クエリを素直に再帰的に振り分けて行くことは思いついたのに…。