Codeforces #942 : Div1 D. Long Way to be Non-decreasing

ライブラリを整えて良かった。
https://codeforces.com/contest/1967/problem/D

問題

N要素の整数列Aと、M要素の整数列Bが与えられる。
A,Bの各要素は1～Mの整数値を取る。

Aの要素A[u]をいくつか選び、A[u]をB[A[u]]で置き換える処理を任意回数行えるとする。
Aを単調増加にするために、最小何回操作が必要か。

解法

あらかじめBをv→B[v]となるFunction Graphとみなし、a→bに遷移可能か、また可能なら最小距離を高速に求められるように前処理しておく。
あとは解答mを総当たりしよう。
A[1]から順にみて行き、A[i]の値を決めるときは、A[i-1]、A[i-1]+1、A[i-1]+2.....を順にm回以内の遷移で到達可能かを順にみて行けばよい。

int T,N,M;
int A[1010101],B[1010101];
int isroot[1010101];
vector<int> C[1010101];
int D[1010101];
int id;
int L[1010101],R[1010101];

template<int NV> struct FunctionGraph {
	int E[NV];
	int N;
	int NG;
	int nex[61][NV];  // 2^i先の点
	vector<int> RE[NV]; // 逆向き辺
	vector<int> G[NV]; // 閉路
	int GS[NV]; // 閉路長
	int Gid[NV],Gindex[NV]; // 閉路IDとその中のindex。閉路外の場合、閉路IDは最寄りの閉路だがindexは-1
	int GV[NV], D[NV]; //最寄りの閉路の点とそこまでの距離
	void dfs(int cur,int id,int d) {
		GV[cur]=id;
		Gid[cur]=Gid[id];
		D[cur]=d;
		FORR(e,RE[cur]) if(Gindex[e]==-1) dfs(e,id,d+1);
	}
	int move(int cur,ll step) { // step先に進む
		int i;
		FOR(i,60) if(step&(1LL<<i)) cur=nex[i][cur];
		return cur;
	}
	void build(int N_) {
		N=N_;
		int i,j;
		vector<int> in(N);
		FOR(i,N) {
			RE[i].clear();
			G[i].clear();
			Gindex[i]=-2;
			nex[0][i]=E[i];
		}
		NG=0;
		FOR(i,N) {
			RE[E[i]].push_back(i);
			in[E[i]]++;
		}
		queue<int> Q;
		FOR(i,N) if(in[i]==0) Q.push(i);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop();
			Gindex[cur]=-1;
			if(--in[E[cur]]==0) Q.push(E[cur]);
		}
		FOR(i,N) if(Gindex[i]==-2) {
			G[NG].push_back(i);
			while(1) {
				int x=G[NG].back();
				Gid[x]=NG;
				Gindex[x]=G[NG].size()-1;
				x=E[x];
				if(x==G[NG][0]) break;
				G[NG].push_back(x);
			}
			GS[NG]=G[NG].size();
			NG++;
		}
		FOR(i,N) if(Gindex[i]>=0) dfs(i,i,0);
		FOR(j,60) FOR(i,N) nex[j+1][i]=nex[j][nex[j][i]];
	}
};
FunctionGraph<1010101> fg;
void dfs(int cur,int d) {
	D[cur]=d;
	L[cur]=id++;
	FORR(e,C[cur]) dfs(e,d+1);
	R[cur]=id;
	
}

int can(int s,int t,int k) {
	if(s==t) return 1;
	if(fg.Gid[s]!=fg.Gid[t]) return 0;
	int root=fg.G[fg.Gid[s]][0];
	int nex=B[root];
	
	
	if(L[t]<L[s]&&L[s]<R[t]) {
		return (D[s]-D[t]<=k);
	}
	else if(L[nex]<L[t]||R[t]<=L[nex]) {
		return 0;
	}
	else {
		return (D[s]+1+D[nex]-D[t]<=k);
	}

}

int ok(int v) {
	if(v<0) return 0;
	int cur=0;
	int i;
	FOR(i,N) {
		while(cur<M&&can(A[i],cur,v)==0) cur++;
		if(cur==M) return 0;
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(j,T) {
		cin>>N>>M;
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
		}
		FOR(i,M) {
			cin>>B[i];
			B[i]--;
			fg.E[i]=B[i];
			C[i].clear();
		}
		fg.build(M);
		FOR(i,M) if(fg.Gindex[i]!=0) C[B[i]].push_back(i);
		id=0;
		FOR(i,M) if(fg.Gindex[i]==0) dfs(i,0);
		
		if(ok(M)==0) {
			cout<<-1<<endl;
			continue;
		}
		int ret=M;
		for(i=20;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i;
		cout<<ret<<endl;
		
		
		
	}
}

まとめ

二分探索内の処理がO(N+M)になるんだな。