Indeedなう（本選B） : E - Line up!

Dより簡単じゃないですかね…。
http://indeednow-finalb-open.contest.atcoder.jp/tasks/indeednow_2015_finalb_e

問題

N要素の数列H[i]がある。
隣接２要素をスワップして、数列を昇順にしたい。
ただし隣接要素をスワップするには、２要素のうち小さい方の値だけコストがかかる。

条件を満たす最小コストを求めよ。

解法

H[i]に同じ要素が複数あると条件を満たせない。
以後、H[i]がすべて異なる場合を考える。

H[i]に対し、j＜iかつH[j]＞H[i]となるjの個数を求め、その個数とH[i]を掛けたものがH[i]をそれより大きな数字とスワップするコストとなる。
よって各iに対し上記jの個数を求めればよい。

これはH[i]を座標圧縮すれば、あとはSegTreeなりBITで解ける。

int N;
ll H[101000];
map<int,int> M;

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;}
};
BIT<int,20> bt;
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>H[i];
		if(M[H[i]]>0) {
			cout<<-1<<endl;
			return;
		}
		M[H[i]]=1;
	}
	x=0;
	ITR(it,M) it->second=++x;
	FOR(i,N) {
		ret += H[i]*(i-bt.total(M[H[i]]));
		bt.add(M[H[i]],1);
	}
	cout<<ret<<endl;
}

まとめ

わりとすんなり。