PKU 1990 - MooFest

問題文 : MooFest

解法 :
2匹の牛について、離れている距離*Max(牛iの聴力, 牛jの聴力)が必要な声のレベルなので、
(全ての声の大きさの総和) = 最も聴力が必要な牛 * 離れている距離の総和 + 次に聴力が必要な牛 * 離れている距離の総和 + ... となる.

ゆえに, 聴力の閾値を降順でソートし, 総和をBITで求めてやれば良い.
ここで, 牛iがいる位置xiと他の点との位置関係は, xi > xjまたはxi < xjとなるので, それを考慮してBITを構築する.

具体的には, BITを配列のように使用し, xi未満の点の総和とxi以上の点の総和をO(log(Max(xi)))時間で求められるようにすればよい.

以上の方法で総和を求めれば, O(Nlog(Max(xi)))時間でこの問題を解く事が出来る.

コード :

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long lint;
int n;

lint c[20001], d[20001];

lint sum(lint *bit, int k)
{
	lint res = 0;
	while (k > 0){
		res += bit[k];
		k -= k & -k;
	}
	
	return (res);
}

void add(lint *bit, int k, lint x)
{
	while (k <= 20001){
		bit[k] += x;
		k += k & -k;
	}
}

int main()
{
	pair<int, int> cow[20000];
	int ma = 0;
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		scanf("%d %d", &cow[i].first, &cow[i].second);
		ma = max(cow[i].second, ma);
	}
	
	for (int i = 0; i < n; i++){
		add(c, cow[i].second, 1);
		add(d, cow[i].second, cow[i].second);
	}
	
	sort(cow, cow + n);
	reverse(cow, cow + n);
	
	lint ans = 0;
	
	for (int i = 0; i < n; i++){
		add(d, cow[i].second, -cow[i].second);
		add(c, cow[i].second, -1);
		lint bigNum = sum(c, ma) - sum(c, cow[i].second - 1), bigVal = sum(d, ma) - sum(d, cow[i].second - 1);
		lint smlNum = sum(c, cow[i].second - 1), smlVal = sum(d, cow[i].second - 1);
		ans += cow[i].first * ((smlNum * cow[i].second - smlVal) + (bigVal - bigNum * cow[i].second));
	}
	
	printf("%lld\n", ans);
	
	return (0);
}