AUPC 2018 day3 B: Pivots

問題

数列a0, ..., an-1が与えられる。要素は互いにことなる。
この数列に対してQ個のクエリを処理した後の数列を出力せよ。
クエリ：　値vが与えられる。ai = vとしたとき、
数列を ai+1, ..., an-1, ai, a0, ..., ai-1のように並び替える。

制約

n, q≦10^5

方針

数列を双方向リストでもつ。クエリは値なので、並び替えをしても値へのポインタをもっておける。
並び替えは繋ぎ変えをすればクエリが一つO(1)で処理できる。

とはいえ実装がかなり面倒だった。平衡二分木ライブラリでやったほうが楽かもしれない。

ソースコード

const int MX = 100020;
int L[MX], R[MX], n, q;

int main() {
	cin >> n >> q;
	using vi = vector<int>;

	vi v(n);
	rep(i, n) cin >> v[i];
	vi vs = v;
	sort(all(vs));
	rep(i, n){
		v[i] = 1 + lower_bound(all(vs), v[i]) - vs.begin();
	}
	rep(i, n + 1){
		int x = i ? v[i - 1] : 0;
		L[x] = i > 1 ? v[i - 2] : 0;
		R[x] = i < n ? v[i] : n + 1;
	}
	L[n + 1] = v[n - 1];
	#if 0
	cerr<<endl;
	rep(i, n+1) cerr<<v[i]<<(i==n?"\n":" ");
	rep(i, n + 1) cerr<<i<<" "<<L[i]<<" "<<R[i]<<endl;
	#endif
	while(q--){
		int x; cin >> x;
		if(n == 1) continue;

		x = 1 + lower_bound(all(vs), x) - vs.begin();
		int a = R[0], A = L[x], b = R[x], B = L[n + 1];
		if(A > 0 && b <= n){
			//cerr<<"! "<<a<<" "<<A<<" "<<x<<" "<<b<<" "<<B<<endl;
			R[0] = b; L[b] = 0;
			R[B] = x; L[x] = B;
			R[x] = a; L[a] = x;
			R[A] = n + 1; L[n + 1] = A;
		}
		else if(b == n + 1){
			R[0] = x; L[x] = 0;
			R[x] = a; L[a] = x;
			R[A] = n + 1; L[n + 1] = A;
		}
		else if(A == 0){
			R[0] = b; L[b] = 0;
			R[B] = x; L[x] = B;
			R[x] = n + 1; L[n + 1] = x;
		}
		else assert(0);
	}
	int r = 0;
	rep(i, n){
		r = R[r];
		cout << vs[r - 1] << (i == n-1?"\n":" ");
	}

	return 0;
}