AtCoder ARC #125 : C - LIS to Original Sequence

D問目まではスムーズだったんだけどね。
https://atcoder.jp/contests/arc125/tasks/arc125_c

問題

1～Nの部分列である数列Aが与えられる。
1～Nの順列のうち、LISの1つにAが現れるようなもので辞書順最小のものを構築せよ。

解法

LISを求める手続きを考えつつ、LISの値を変えない範囲で小さい値を挿入することを考える。
今A[i]=p、A[i+1]=qとする。pとqの間にどんな要素を挿入できるかを考えよう。

求めたいのは辞書順最小なので、p未満の値のうち未確定なものを挿入することを考える。(p以上のものを挿入すると明らかにLISが長くなるので不可)
LISを求める手続きでは、配列を更新していくことになる。この数列をBとする。
その際、その数列は、A[i]=pが確定した段階でB[i]=pとなり、その後B[i+1]=qとなる。
その間、p未満の未確定の値があれば、B[0]～B[i]の間に昇順となるように挿入していけばよい。

Aの末尾の要素まで確定させる間に、挿入できず余った値がある場合、Aの末尾の要素より大きいものはその直前、小さいものはその直後に降順で挿入しよう。

int N,K;
int A[202020];

int B[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	set<int> S;
	FOR(i,N) S.insert(i+1);
	FOR(i,N+1) B[i]=N+2;
	
	FOR(i,K) {
		cin>>A[i];
		S.erase(A[i]);
	}
	vector<int> R;
	FOR(i,K) {
		while(S.size()) {
			x=*S.begin();
			if(x>A[i]) break;
			
			y=lower_bound(B,B+N+1,x)-B;
			if(y>=i) break;
			B[y]=x;
			R.push_back(x);
			S.erase(x);
		}
		assert(B[i]>A[i]);
		B[i]=A[i];
		R.push_back(A[i]);
	}
	
	while(S.size()) {
		x=*S.rbegin();
		if(x<R.back()) break;
		S.erase(x);
		R.push_back(x);
		swap(R[R.size()-1],R[R.size()-2]);
		
	}
	while(S.size()) {
		x=*S.rbegin();
		S.erase(x);
		R.push_back(x);
	}
	
	FORR(r,R) cout<<r<<" ";
	cout<<endl;
	
}

まとめ

これは本番すんなり解けたね。