AtCoder ARC #165 : F - Make Adjacent

最近のARC Fの中では実装が軽め？
https://atcoder.jp/contests/arc165/tasks/arc165_f

問題

1～Nが2回ずつ現れる数列Xが与えられる。
隣接2要素のswapを繰り返し、Xで同じ値が2個ずつ続くようにしたい。
swap回数が最小のもののうち、辞書順最小のものを求めよ。

解法

2つの値の相対的な位置関係が

• AABB → AAがBBの前に来るのが良い
• ABAB → AAがBBの前に来るのが良い
• ABBA → AAとBBどちらが前でも良い。Xを辞書順最小にしたいので、値が小さい方が前に来てほしい

Xを前から決めていくことを考える。
よって、ABCDDCBAのように各値vについて、vより手前に1回目が登場する値は、2回目の登場がvの2回目以降であるような値は、次にXの先頭に持って行ってもswap回数最小が維持できる。

これをSegTreeに載せよう。

SegTreeの添え字は元々のXの添え字と同じ。
SegTreeの各ノードには、

• 区間内に現れる位置未確定の値のうち、2回目の登場位置の最小値
• 区間内に現れる位置未確定の値で次に先頭に持ってこれない値のうち、2回目の登場位置の最小値。値がなければ無限大。

を載せよう。

まず、後者の値が無限大にならない限り、後者の値に対応する値を、Xの先頭に持ってくる可能な候補として繰り返し抽出する。
次に、候補の中で最小値をXの未確定要素のうち先頭とする。(これにより、前ステップで新たな候補が増え得る)
これをN回繰り返せばよい。

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){
		pair<V,int> a=l;
		a.first.first=min(l.first.first,r.first.first);
		if(l.first.first>r.first.second) {
			a.first.second=r.first.second;
			a.second=r.second;
		}
		return a;
	}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(make_pair(1<<30,1<<30),1<<30);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	void update(int entry, V v) {
		entry += NV;
		val[entry]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_Pair<pair<int,int>,1<<20> st;
int N;
int A[404040];
int L[202020],R[202020];
int num[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(L);
	cin>>N;
	FOR(i,2*N) {
		cin>>A[i];
		A[i]--;
		if(L[A[i]]<0) {
			L[A[i]]=i;
		}
		else {
			R[A[i]]=i;
		}
	}
	FOR(i,2*N) {
		if(L[A[i]]==i) {
			st.update(i,{R[A[i]],R[A[i]]});
		}
	}
	set<int> cand;
	while(1) {
		while(1) {
			auto p=st.val[1];
			i=p.second;
			if(p.first.second==1<<30) break;
			cand.insert(A[i]);
			st.update(i,{R[A[i]],1<<30});
		}
		if(cand.empty()) break;
		x=*cand.begin();
		cand.erase(x);
		cout<<x+1<<" "<<x+1<<" ";
		st.update(L[x],{1<<30,1<<30});
	}
	cout<<endl;
}

まとめ

ちょっとSegTreeの作り方が難しい。