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; }