POJ 1990: MooFest

概要

一次元座標x[i]と,値v[i]が与えられる.iとjの間の通信コストはmax(v[i],v[j])*|x[i]-x[j]|である.コストの総和を求めよ

解法

座標でソートしておく.
各iについて,BITを用いてv[i]以下であるiより小さい場所の座標の総和とそのような場所の個数を計算する.

const int M = 20010;
int N;
pair<ll, ll> c[20010];

ll bit1[20010], bit2[20010];

void init(){
	memset(bit1, 0, sizeof(bit1));
	memset(bit2, 0, sizeof(bit2));
}
pair<ll,ll> sum(int x){
	ll r1 = 0, r2 = 0;
	while(x > 0){
		r1 += bit1[x];
		r2 += bit2[x];
		x -= x & -x;
	}
	return make_pair(r1, r2);
}
void add(int x, ll v){
	while(x < M){
		bit1[x] += v;
		bit2[x] += 1;
		x += x & -x;
	}
}

main(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		ll v, x;
		scanf("%lld%lld", &v, &x);
		c[i] = make_pair(x, v);
	}
	sort(c, c + N);
	ll res = 0LL;
	init();
	for(int i=0;i<N;++i){
		//printf("%lld,%lld\n", c[i].first, c[i].second);
		pair<ll, ll> r = sum(c[i].second);
		//printf("[%lld, %lld]\n", r.first, r.second);
		res += c[i].second * (r.second*c[i].first-r.first);
		add(c[i].second, c[i].first);
	}
	//printf("%lld\n", res);
	init();
	for(int i=N-1;i>=0;--i){
		pair<ll, ll> r = sum(c[i].second-1);
		res += c[i].second * (r.first-r.second*c[i].first);
		add(c[i].second, c[i].first);
	}
	printf("%lld\n", res);
	return 0;
}