POJ 1990 MooFest 题解 《挑战程序设计竞赛》

POJ 1990 MooFest

奶牛节：N头奶牛每头耳背程度v，坐标x。两牛交流需要音量为distance * max(v(i),v(j))，求所有牛两两交流所需总和？

3.3活用各种数据结构

Binary Indexed Tree

要求{∀i with v[i]<v[j]} Σv[j]*|x[i]-x[j]|，也就是求 Σv[j]*(x[j]-x[i])_{{∀i with v[i]<v[j] and x[i]<x[j]}} + Σv[j]*(x[i]-x[j])_{{∀i with v[i]<v[j] and x[j]<x[i]}}。这里涉及到求和，而且求和的区间有重复，所以要利用树状数组。

这题用到了两个BIT，分别是个数BIT和距离BIT。将牛按照耳背程度升序后，一头一头地加入奶牛节。加入每一头的时候，这头牛的耳背程度肯定是最大的。那么就用这头牛的耳背程度乘以到所有牛的距离即可。每加入一头牛，就逐步构建BIT一次。

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_N 20000 + 16
typedef long long LL;

pair<int, int> cow[MAX_N];
int N;
LL count_bit[MAX_N], distance_bit[MAX_N];	// 两个数组下标都是坐标，值用来统计牛的个数和距离

// 求和sum{a[t], 0 <= t <= i}
LL sum(LL* bit, int i)
{
	LL s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}

	return s;
}

// 求和a[from, to)
LL sum(LL* bit, int from, int to)
{
	return sum(bit, to - 1) - sum(bit, from - 1);
}

// 执行 a[i] += x
void add(LL* bit, int i, LL x)
{
	while (i <= MAX_N)
	{
		bit[i] += x;
		i += i & -i;
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> cow[i].first >> cow[i].second;
	}

	sort(cow, cow + N);
	LL result = 0;
	for (int i = 0; i < N; ++i)
	{
		// cow按v升序，v始终为最大
		int v = cow[i].first, x = cow[i].second;	// 自己的参数，取个短点好懂的名字
		LL left = sum(count_bit, 1, x), right = sum(count_bit, x + 1, MAX_N);	// 左右牛的个数
		result += v * ((left * x - sum(distance_bit, 1, x)) + (sum(distance_bit, x + 1, MAX_N) - right * x));
		add(count_bit, cow[i].second, 1);
		add(distance_bit, cow[i].second, cow[i].second);
	}
	cout << result << endl;

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1990 MooFest 题解 《挑战程序设计竞赛》