AtCoder ARC #031 : C - 積み木

既視感のある問題。
http://arc031.contest.atcoder.jp/tasks/arc031_3

問題

互いに長さの異なるN個の積木が一列に並んでおり、それぞれの高さはA[i]である。
隣接する積木を入れ替える、という作業を何度か行い、最終的に最大の高さの積木をA[t]として
A[0] ＜ A[1] ＜ ... ＜ A[t] ＞ ... ＞ A[N-1]
となるようにしたい。
最小で何回入れ替えればよいか。

解法

GCJ2014で同じ問題が出ている。
Google Code Jam 2014 Round 2 : B. Up and Down - kmjp's blog

ただし、GCJに比べNの上限が100倍であり、O(N^2)の解法は取れない。
上記解法に則ると、A[i]に対しA[0]～A[i-1]とA[i+1]～A[N-1]のうちA[i]より高い積木の数をカウントし、数の少ない方に移動させればよい。

これにはBITをA[0]から増分方向およびA[N-1]から減少方向にBITに要素A[i]を追加していくことでそれぞれカウントできる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,20> bt[2];

int N;
int B[100500];
int num[2][100050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>B[i];
	
	FOR(i,N) {
		num[0][i]=bt[0].total(100100-B[i]);
		bt[0].update(100100-B[i],1);
	}
	for(i=N-1;i>=0;i--) {
		num[1][i]=bt[1].total(100100-B[i]);
		bt[1].update(100100-B[i],1);
	}
	ll ret=0;
	FOR(i,N) ret+=min(num[0][i],num[1][i]);
	cout << ret << endl;
}

まとめ

本番６分足らずで解けている。
GCJがなければもっと迷ったかも。