CODE FESTIVAL 2018 Final : J - Complicated Operations

しんどかったです…。
https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_j

問題

N(2の累乗)要素からなる２つの数列S[0],Tが与えられる。
i回目の処理では、以下の手順でS[i]を生成できる。

• 2つのi未満のindex x,yを選択する。また、整数fを定める。
• S[i][j] = S[x][j]またはS[y][j-f]のいずれを取るか、j毎に選択できる。

500回以内にS[i]=Tを構築する手順を答えよ。

解法

Editorialの記述が少ないので、Editorial見て解法にたどり着くのは結構大変。
Writer解を見るに、以下の手順を踏んでいる。

まず、Tに現れる要素が全てS[0]のどこかに現れていることを確認しよう。

SとTの要素が並べ替えだけで一致するとは限らないので、一部要素は登場回数を増減させる必要がある。
並べ替えと増減を一気に行うのは難しいので、別々に行うことにしよう。
仮にS[0]="1 6 4 8 7 2 5 3"、T="1 3 3 7 3 1 3 3"とする。この場合、中に1が2個、3が5個、7が1個含まれている。
以下のようにまずS[0]のうち必要な要素を並べ替え、その後Tの登場回数分だけ増幅させる。
そして再度並べ替えて所定の位置に合わせよう。

S[0]= 1 6 4 8 7 2 5 3 
        ↓並べ替え
S[a] = 1 * 3 * * * * 7 
        ↓　複製
S[b] = 1 1 3 3 3 3 3 7
       ↓並べ替え
T    = 1 3 3 7 3 1 3 3

複製はO(logN)回の処理で行える。
あと２回の並べ替えは同じロジックで対応できる。
(国内のみのコンテストのため解答例もないが、Write解含め多くの例で似た処理を２回やっているのはそのため)

並べ替えはO(log^2 N)回の処理で対応できる。
1つ目のlogだが、初回のループでN個中前半に来るべきN/2個を前半、後半に来るべきN/2個を後半に持っていく。
２回目のループでは、それぞれのN/2個内で、前半に来るべきN/4個を前半、後半に来るべきN/4個を後半に持っていく…
という要領を繰り返せばよい。

次に、個々のループで「N個中前半に来るべきN/2個を前半、後半に来るべきN/2個を後半に持っていく」ができればよい。
こちらもO(log N)回の処理で対応できる。
i回目のループでは、各要素の位置をmod 2^iで分類したとき、前半にくべきN/2個の数と後半にくべきN/2個の数が均等になるようにし、その際「前半にくべきN/2個」ができるだけ前に来るようにしよう。
そのためには、A[x]とA[x | (2^(i-1)]を比較する。
両者のうち片方が前半、片方が後半にあるようなケースがいくつかあったとする。(その数は必ず偶数である)
その場合、xの小さい順半分のケースでは、前半にくべきものを前半、残り半分では前半にくべきものを後半に持っていく。
そうすると、「前半にくべきN/2個の数と後半にくべきN/2個の数が均等になるようにし、その際「前半にくべきN/2個」ができるだけ前に来る」ようになる。

なお、要素のswapはf=(2^(i-1))とf=-(2^(i-1))の2手でできる。

ab
↓  (f = -1)でaを右にコピー
aa
↓  (f = 1)で2手前のbを左にコピー
ba

int N;
int S[505][9090];
int T[9090];
int pos[9090];
vector<int> D[9090];

vector<pair<ll,string>> event;

void add(int x,int y,int f,string T) {
	ll key=1LL*x*1000000000LL+1LL*y*100000+(f+10000);
	event.push_back({key,T});
	
	int cur=event.size();
	assert(x>=0 && y>=0 && x<cur && y<cur && T.size()==N);
	
	int i;
	FOR(i,N) {
		if(T[i]=='x') S[cur][i]=S[x][i];
		else {
			assert(i-f>=0 && i-f<N);
			S[cur][i]=S[y][i-f];
		}
	}
}

void hoge(vector<int> dest) {
	int i;
	
	for(int step=N/2;step>=1;step/=2) {
		vector<int> NS(N);
		FOR(i,N) NS[i]=(dest[i]&step)!=0;
		for(int sh=1;sh<=step;sh*=2) {
			string C[2];
			C[0]=C[1]=string(N,'x');
			
			for(int cur=0;cur<N;cur+=step*2) {
				for(int dif=0;dif<sh;dif++) {
					int notsame=0;
					for(i=cur+dif;i<cur+(step*2);i+=sh*2) {
						if(NS[i]!=NS[i^sh]) notsame++;
					}
					notsame/=2;
					
					for(i=cur+dif;i<cur+(step*2);i+=sh*2) {
						if(NS[i]==0 && NS[i^sh]==1) {
							if(sh!=step && notsame<=0) {
								swap(NS[i],NS[i^sh]);
								swap(dest[i],dest[i^sh]);
								C[0][i^sh]='y';
								C[1][i]='y';
							}
							notsame--;
						}
						else if(NS[i]==1 && NS[i^sh]==0) {
							if(sh==step || notsame>0) {
								swap(NS[i],NS[i^sh]);
								swap(dest[i],dest[i^sh]);
								C[0][i^sh]='y';
								C[1][i]='y';
								notsame--;
							}
						}
					}
				}
			}
			int cur=event.size();
			add(cur,cur,sh,C[0]);
			add(cur+1,cur,-sh,C[1]);
		}
	}
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	MINUS(pos);
	FOR(i,N) {
		cin>>S[0][i];
		S[0][i]--;
		pos[S[0][i]]=i;
	}
	FOR(i,N) {
		cin>>T[i];
		T[i]--;
		if(pos[T[i]]==-1) return _P("-1\n");
		D[T[i]].push_back(i);
	}
	
	vector<int> dest(N,-1);
	set<int> unused;
	FOR(i,N) unused.insert(i);
	int ok=0;
	FOR(i,N) {
		if(D[i].size()>0) {
			unused.erase(ok);
			dest[pos[i]]=ok;
			ok+=D[i].size();
		}
	}
	FOR(i,N) if(dest[i]==-1) {
		dest[i]=*unused.begin();
		S[0][i]=-1;
		unused.erase(unused.begin());
	}

	hoge(dest);
	
	vector<int> from(N,0);
	int pre=0;
	FOR(i,N) {
		if(S[event.size()][i]>=0) pre=i;
		else from[i]=i-pre;
	}
	
	for(int step=1;step<=N/2;step*=2) {
		string T=string(N,'x');
		FOR(i,N) if((from[i]&step)&&step*2>from[i]) T[i]='y';
		add(event.size(),event.size(),step,T);
	}
	
	FOR(i,N) {
		dest[i]=D[S[event.size()][i]].back();
		D[S[event.size()][i]].pop_back();
	}

	hoge(dest);

	FOR(i,N) assert(S[event.size()][i]==T[i]);
	cout<<event.size()<<endl;
	FORR(e,event) {
		ll x=e.first/1000000000LL;
		ll y=e.first/100000LL%10000;
		ll f=e.first%100000-10000;
		cout<<x<<" "<<y<<" "<<f<<" "<<e.second<<endl;
	}
	
}

まとめ

もう少しEditorial書いて欲しいです…理解するのに苦労した。