一、题面
二、分析
一个简单的树状数组运用。首先要把样例分析清楚，凑出57，理解一下。
然后可以发现，如果每次取最大的v就可以肆无忌惮的直接去乘以坐标差值就可以了，写代码的时候是反着来的，好操作一点。
1.根据每个点的v值进行从小到大的排序。
2.排序后从小到达进行处理，重点是处理坐标的差值和。
3.取出一个点后，先用树状数组（需要不断的加入点进行维护）算出坐标小于等于这个点的坐标和，记为$Sum$。
4.算出坐标小于等于这个点的坐标的数量，极为$Count$。
5.现在可以算出所有坐标小于等于该点的坐标差值之和（所有已经维护的点）。利用公式
$ansLeft = v * (Count * x - Sum)$
这个就是小于坐标x（即x坐标左边）的答案。
6.还需要求出x右边的差值和，这里直接维护一个所有加入点的坐标和$total$，并且比较容易推出大于x坐标的点的数量为$i - Count$。需要注意的是这里的$i$是当前点的下标，那么就是除去当前点的所有已经加入点的数量。（可能说的不太清楚，可以画一画，体会一下）。
7.推导出右边的和。
$ansRight = v * [total - Sum - (i - Count) * x]$
8.更新答案
$ans = ansLeft + ansRight$
更新total
$total += x$
维护树状数组
然后回到3进行循环处理即可。
9.得出最终答案$ans$。
三、AC代码
1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <algorithm>
5
6 using namespace std;
7
8 const int MAXN = 2e4 + 10;
9 typedef long long LL;
10
11 struct Node
12 {
13 int x, v;
14 bool operator < (const Node & t)const
15 {
16 return v < t.v;
17 }
18 }Data[MAXN];
19
20 int countBIT[MAXN]; //统计个数 MAXN其实是坐标最大
21 int sumBIT[MAXN]; //统计坐标值
22 int N;
23
24 int getSum(int x, int *arr) //BIT求和
25 {
26 int ans = 0;
27 while(x)
28 {
29 ans += arr[x];
30 x -= x & (-x);
31 }
32 return ans;
33 }
34
35 void add(int x, int val, int *arr) //单点更新
36 {
37 while(x < MAXN)
38 {
39 arr[x] += val;
40 x += x & (-x);
41 }
42 }
43
44 LL solve()
45 {
46 LL ans = 0;
47 LL total = 0;
48 memset(countBIT, 0, sizeof(countBIT));
49 memset(sumBIT, 0, sizeof(sumBIT));
50 sort(Data, Data + N);
51
52 //v值从小到大进行处理
53 for(int i = 0; i < N; i++)
54 {
55 LL Count = getSum(Data[i].x, countBIT); //比坐标x小的数量
56 LL Sum = getSum(Data[i].x, sumBIT); //坐标<=x的坐标和
57
58 //+left
59 ans += Data[i].v * (Count * Data[i].x - Sum);
60 //+right
61 ans += Data[i].v * (total - Sum - (i - Count) * Data[i].x);
62 total += Data[i].x;
63 add(Data[i].x, 1, countBIT);
64 add(Data[i].x, Data[i].x, sumBIT);
65 }
66 return ans;
67
68 }
69
70 int main()
71 {
72
73 while(scanf("%d", &N) != EOF)
74 {
75 for(int i = 0; i < N; i++)
76 {
77 scanf("%d %d", &Data[i].v, &Data[i].x);
78 }
79 printf("%lld\n", solve());
80 }
81 return 0;
82 }