AtCoder ARC #080 : E - Young Maids

E手間取るしF解けないし微妙な出来。
http://arc080.contest.atcoder.jp/tasks/arc080_c

問題

1～Nの順列である数列Pがある。ここから別の数列Qを構築することを考える。
ここから連続する2要素(a,b)を選び、Pから抜き出してQの先頭に(x,y)の順で追加する。
こうして構築できるQのうち辞書順最小のものを求めよ。

解法

Pの部分列P[L...R]に関し、そこから上記手段で構築できる辞書順最小のものを考える。
辞書順最小となるには、最後に残る２要素(P[a],P[b])が最小となるようにすればよい。
そのためにはそれまでにそれ以外の要素を消す必要がある。

よってP[L...(a-1)],P[(a+1)...(b-1)],P[(b+1)...R]がいずれも偶数長でなければならない(空でもよい)。
辞書順最小な値を選ぶことから、まず条件を満たすaを求めよう。
それはL≦a＜Rで(a-L)が偶数なもののうちP[a]が最小のものである。
aが決まると同様にbも求めることが出来、a≦b＜RでP(b-a)が奇数なもののうちP[b]が最小のものである。

a,bはindexが偶奇縛りがある中で値の最小値を求めることになる。
よって、indexの偶奇別に2つRMQのデータ構造を作っておけばよい。

さて、P[L...R]から(P[a],P[b])を先に取り除くと、以後はP[L...(a-1)],P[(a+1)...(b-1)],P[(b+1)...R]の３つについて処理を行うことになる。
各数列はどの順で処理を行ってもよい。
よって以下のようにする。

処理対象の部分列P[L...R]に対し、それぞれ取り除く要素の候補(P[a],P[b])を求め、set等で最小値を管理する。
複数の部分列が残っているとき、最小値を取り除ける部分列P[L'...R']を選び、対応する(P[a'],P[b'])を解の末尾に追加しよう。
その後、P[L'...(a'-1)],P[(a'+1)...(b'-1)],P[(b'+1)...R']の3つの部分列に対し、それぞれ対応する取り除く要素の候補を求めてsetに放り込めばよい。

int N;
int A[202020];
int rev[202020];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=303030;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_1<int,1<<20> ev,od;
set<vector<int>> cand;

void add(int L,int R) {
	vector<int> ret;
	if(R<=L) return;
	
	int tar;
	if(L%2==0) tar=ev.getval(L,R);
	else tar=od.getval(L,R);
	int x=rev[tar];
	ret.push_back(tar);
	
	if((x+1)%2==0) tar=ev.getval(x+1,R);
	else tar=od.getval(x+1,R);
	int y=rev[tar];
	ret.push_back(tar);
	
	ret.push_back(L);
	ret.push_back(x);
	ret.push_back(y);
	ret.push_back(R);
	cand.insert(ret);
}

void dodo(vector<int> V) {
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		if(i%2==0) {
			ev.update(i,A[i]);
			od.update(i,1<<20);
		}
		else {
			od.update(i,A[i]);
			ev.update(i,1<<20);
		}
		rev[A[i]]=i;
	}
	
	vector<int> Q;
	
	add(0,N);
	while(cand.size()) {
		vector<int> v=*cand.begin();
		cand.erase(cand.begin());
		Q.push_back(v[0]);
		Q.push_back(v[1]);
		add(v[2],v[3]);
		add(v[3]+1,v[4]);
		add(v[4]+1,v[5]);
	}
	
	
	FOR(i,N) _P("%d%c",Q[i],(i==N-1)?'\n':' ');
	
}

まとめ

1000ptでもよさそうと思ったけど盛りすぎ？