AtCoder ARC #043 : C - 転倒距離

方針はそこそこの時間に思いついたけど、バグとりに手こずった。
http://arc043.contest.atcoder.jp/tasks/arc043_c

問題

２つの同サイズの数列における転倒距離とは、両数列内で登場位置の前後関係が異なる要素の対の数を示す。

1～Nのpermutationである２つの数列A,Bが与えられる。
A,B双方から等転倒距離にある数列が存在すれば、それを答えよ。

問題

まずAの中身が[0, 1, 2 ...]と昇順になるようA,Bの内容をRenumberする。
この状態でBの転倒数を求め、Aからの転倒数がその半分になるような数列を作ればよい。

そのためには、まずBの各要素において、その右側にある小さい要素数を数え上げる。
これはBIT等を使いO(logN)で求められる。

あとは上記(右側にある小さい要素数)を合計が半分になるまで減らし、減らした(右側にある小さい要素数)から数列を復元すればよい。
自分の解法はO(N^1.5)だけど何とか間に合う。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> bt;

ll rev;

int N;
int A[101010],B[101010];
int mp[101010];
ll inv[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], mp[A[i]]=i;
	FOR(i,N) cin>>B[i], B[i]=mp[B[i]];
	
	for(i=N-1;i>=0;i--) {
		inv[B[i]]=bt.total(B[i]);
		rev += inv[B[i]];
		bt.add(B[i],1);
	}
	
	if(rev%2==1) return _P("-1\n");
	
	rev/=2;
	vector<int> V;
	for(i=N-1;i>=0;i--) {
		x=min(rev,inv[i]);
		inv[i]-=x;
		rev-=x;
	}
	FOR(i,N) V.insert(V.end()-inv[i],A[i]);
	FOR(i,N) _P("%d%c",V[i],(i==N-1)?'\n':' ');
}

まとめ

自分の解法は最初O(N^2)だと思っていたので、部分点しか取れないと思ったらACが出てびっくり。