POJ 1990 MooFest

問題
http://poj.org/problem?id=1990

解法
x座標に関してBIT木を使っていろいろやる

#include <cstdio>
#include <algorithm>
#define fst first
#define snd second
using namespace std;

const int MAX_N = 20000;
const int MAX_X = 20002;
typedef pair<int,int> P;
P cows[MAX_N];
int c[MAX_X];
int x[MAX_X];
int N;

long long sum(int a[MAX_X], int n){
	long long s = 0;
	while(n > 0){
		s += a[n];
		n -= n & -n;
	}
	return s;
}
void add(int a[MAX_X], int i, int x){
	while(i <= MAX_X){
		a[i] += x;
		i += i & -i;
	}
}

int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		int v, x;
		scanf("%d %d",&v,&x);
		cows[i].fst = v;
		cows[i].snd = x;
	}
	sort(cows, cows + N);
	long long ans = 0;
	for(int i=0; i<N; i++){
		int v = cows[i].fst;
		int px = cows[i].snd;
		long long cnt;
		long long sum_x;

		cnt   = sum(c, px);
		sum_x = sum(x, px);
		ans += v * ( cnt*px - sum_x );

		cnt   = sum(c, MAX_X-1) - sum(c, px);
		sum_x = sum(x, MAX_X-1) - sum(x, px);
		ans += v * ( sum_x - cnt*px );

		add(c, px, 1);
		add(x, px, px);
	}
	printf("%lld\n", ans);
	return 0;
}