Codeforces #908 : Div1 B. Neutral Tonality

いまいちだった回。
https://codeforces.com/contest/1893/problem/B

問題

整数列A,Bが与えられる。
Bの各要素をAの任意の場所に挿入し、長さ|A|+|B|の数列Cを作る。
LIS(C)が最少となるようなCの一例を示せ。

解法

AのLISを求めたら、LISが長くならないよう、A[i]＞B[j]となるようなB[j]をA[i]の後に配置しよう。
その際、Bは降順となるように挿入していく。

int T,N,M,A[202020],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>>M;
		vector<int> V;
		FOR(i,N) {
			cin>>A[i];
			x=lower_bound(ALL(V),A[i])-V.begin();
			L[i]=x;
			if(x==V.size()) V.push_back(A[i]);
			else V[x]=A[i];
		}
		V.clear();
		int ma=0;
		for(i=N-1;i>=0;i--) {
			A[i]=-A[i];
			x=lower_bound(ALL(V),A[i])-V.begin();
			R[i]=x;
			if(x==V.size()) V.push_back(A[i]);
			else V[x]=A[i];
			A[i]=-A[i];
			ma=max(ma,1+L[i]+R[i]);
		}
		int LS=N,RS=-1;
		set<int> cand;
		FOR(i,N) if(ma==1+L[i]+R[i]) {
			if(R[i]==0) cand.insert(i);
		}
		multiset<int> X;
		FOR(i,M) {
			cin>>B[i];
			X.insert(B[i]);
		}
		FOR(i,N) {
			if(cand.count(i)) {
				while(X.size()&&*X.rbegin()>=A[i]) {
					cout<<*X.rbegin()<<" ";
					X.erase(X.find(*X.rbegin()));
				}
			}
			cout<<A[i]<<" ";
			if(cand.count(i)) {
				cand.erase(i);
				if(cand.empty()) {
					while(X.size()) {
						cout<<*X.rbegin()<<" ";
						X.erase(X.find(*X.rbegin()));
					}
				}
			}
		}
		cout<<endl;
	}
}

まとめ

方針が思いついても実装がちょっとめんどい。