yukicoder : No.1768 The frog in the well knows the great ocean.

なんとか全完。
https://yukicoder.me/problems/no/1768

問題

2つの整数列A,Bが与えられる。
Aの区間を指定して、それらの値を区間内の最大値に置き換える、という作業を繰り返す。
AをBにできるか判定せよ。

解法

区間指定の最大値の置き換えという作業を、各要素の値を、自身より大きな値に遭遇するまで左右にコピーできると考える。
まず、A[i]を左右どこまで複製できるか求めておく。その範囲を[L[i],R[i]]とする。

C[j] := A[C[j]]を複製してB[i]とする
というようなC[j]を考える。
あとは、C[j]をjの昇順に求めて行こう。

• C[j]は単調増加
• B[j]=A[C[j]]
• j∈[L[C[j]],R[C[j]]]

を満たすようC[j]を貪欲に選んでいくとよい。

int T;
int N;
int A[202020];
int B[202020];
int L[202020],R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> W;
		vector<pair<int,int>> P;
		FOR(i,N) {
			cin>>A[i];
			P.push_back({-A[i],i});
		}
		sort(ALL(P));
		W.insert(-1);
		W.insert(N);
		FOR(i,N) {
			x=P[i].second;
			auto it=W.lower_bound(x);
			R[x]=*it-1;
			L[x]=*prev(it)+1;
			W.insert(x);
		}
		
		
		FOR(i,N) cin>>B[i];
		
		int cur=0;
		FOR(i,N) {
			while(cur<N&&(A[cur]!=B[i]||(i<L[cur]||i>R[cur]))) cur++;
			if(cur==N) break;
		}
		if(i==N) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		
		
	}
}

まとめ

ありそうな問題ではあるけど、過去にないのかな？