傳送門：
MooFest
題意：
| 有 N 頭牟牟牟叫的牛，每隻有一個值 Vi，以及所在的座標值，任兩隻牛要溝通會發出 Max(Vi, Vj) * | Xi - Xj | ，的聲音。 |
求發出的聲音總和。
思路：
因為是求 Max，所以如果依照 Vi 排序，就保證每次加入考慮的牛，都會使用該牛的 Vi 來作為發出聲響的因子，只需要透過資料結構來查詢目前在該牛前與後的牛，坐標和分別為多少，以及有多少隻，就能湊出答案了。
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
inline ll getint(){
ll _x=0,_tmp=1; char _tc=getchar();
while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
if( _tc == '-' ) _tc=getchar() , _tmp = -1;
while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
return _x*_tmp;
}
//////// template end //////////
int N;
pii arr[20005], bit[(1<<15) +1], q1, q2; // BIT : {cnt, sum}
ll ans;
inline pii operator -= (pii& p1, const pii& p2){
p1.X -= p2.X;
p1.Y -= p2.Y;
return p1;
}
inline pii operator += (pii& p1, const pii& p2){
p1.X += p2.X;
p1.Y += p2.Y;
return p1;
}
inline int lower_bit(int& x) { return x&(-x); }
inline pii query(int v){
pii res = bit[v];
for( v-=lower_bit(v) ; v ; v-=lower_bit(v) )
res += bit[v];
return res;
}
inline void add(int val){
pii x = MP(1, val);
for(int v = val ; v <= 1<<15 ; v+=lower_bit(v) )
bit[v] += x;
}
void init(){
N = getint();
for(int i=1;i<=N;i++)
arr[i].X = getint(), arr[i].Y = getint();
ans = 0;
}
void sol(){
sort(arr+1, arr+N+1);
for(int i=1;i<=N;i++){
q1 = query(arr[i].Y); // {cnt, sum}
q2 = query(1<<15);
q2 -= q1;
// q1 : less or equal than this coordinate
ans += arr[i].X * (arr[i].Y * (q1.X - q2.X) - q1.Y + q2.Y);
add(arr[i].Y);
}
cout << ans << endl;
}
int main(){
init();
sol();
}