概要
一次元座標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; }