poj1990 MooFest

思路：

首先把牛按v值排序，然后对于每一头牛i，分别统计v值小于该牛且（1）x值小于该牛的牛数c₁以及这些牛的坐标和x₁；（2）x值大于该牛的牛数c₂以及这些牛的坐标和x₂。将v_i * (x_i * c₁ - x₁) + v_i * (x₂ - x_i * c₂)加入答案中即可。

实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int MAXN = 200005;
 7 const int MAXX = 200005;
 8 struct node
 9 {
10     int v, x;
11 };
12 node a[MAXN];
13 int n;
14 ll bit0[MAXX], bit1[MAXX];
15 inline int lowbit(int x) { return x & -x; }
16 void add(ll * bit, int i, int dx)
17 {
18     while (i <= MAXX) { bit[i] += dx; i += lowbit(i); }
19 }
20 ll sum(ll * bit, int i)
21 {
22     ll ans = 0;
23     while (i) { ans += bit[i]; i -= lowbit(i); }
24     return ans;
25 }
26 bool cmp(const node & a, const node & b)
27 {
28     return a.v < b.v;
29 }
30 int main()
31 {
32     scanf("%d", &n);
33     for (int i = 0; i < n; i++) scanf("%d %d", &a[i].v, &a[i].x);
34     sort(a, a + n, cmp);
35     ll ans = 0;
36     for (int i = 0; i < n; i++)
37     {
38         ll c = sum(bit0, a[i].x), s = sum(bit1, a[i].x);
39         ans += (a[i].x * c - s) * a[i].v;
40         c = sum(bit0, MAXX) - c; s = sum(bit1, MAXX) - s;
41         ans += (s - c * a[i].x) * a[i].v;
42         add(bit0, a[i].x, 1); add(bit1, a[i].x, a[i].x);
43     }
44     printf("%lld
", ans);
45     return 0;
46 }