MooFest, 2004 Open
约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很
多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i 头奶牛的坐标为Xi,没有两头奶牛的坐标是相同的。奶牛们的叫声很大,第i 头和第j 头奶牛交流,会发出max{Vi; Vj}×|Xi − Xj | 的音量,其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。假设每对奶牛之间同时都在说话,请计算所有奶牛产生的音量之和是多少。
输入格式:
• 第一行:单个整数N,1 ≤ N ≤ 20000
• 第二行到第N + 1 行:第i + 1 行有两个整数Vi 和Xi,1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000
输出格式:
• 单个整数:表示所有奶牛产生的音量之和
输入样例#1:
4
3 1
2 5
2 6
4 3
输出样例#1:
57
朴素O(N2)
类似于归并排序的二分O(N logN)
树状数组O(N logN)
V*+abs(a_1-X)+V*abs(a_2-X)+V*abs(a_3-X)+.... \\=V*(abs(a_1-X)+abs(a_2-X)+abs(a_3-X)+.......) \\ =V*(a_1-X+a_2-X+X-a_3) \\ =V*((-N*X+(a_1+a_2+..+a_N)) +M*X-(a_3+...a_M)
推公式的题目 设当前奶牛的音量为V,坐标为X,ai表示第i头奶牛的坐标 假定a1,a2>X,a3<X(方便理解) 我们发现abs不满足分配率(就是abs(a+b)!=abs(a)+abs(b) ) 此时我们分情况讨论 设有n个奶牛的坐标比X大,有m个奶牛的坐标比X小,把上面的abs拆开
那么对于N,M,a1+a2+...,a3+,,, 利用用树状数组求逆序对的思想 我们可以用两个树状数组维护
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<deque>
7 #include<queue>
8 #define LL long long
9 #define lb(x) ((x)&(-x))
10 using namespace std;
11 const LL MAXN=40000001;
12 inline LL read()
13 {
14 char c=getchar();LL x=0,f=1;
15 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
16 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
17 }
18 struct node
19 {
20 LL v,x;
21 }cow[MAXN];
22 LL n;
23 int comp(const node &a,const node &b)
24 {
25 return a.v<b.v;
26 }
27 LL tree_num[MAXN];
28 LL tree_sum[MAXN];
29 LL MAXX;
30 inline void Point_Add(LL pos,LL val,bool how)
31 {
32 while(pos<=MAXX)
33 {
34 if(how==1)tree_num[pos]+=val;
35 else tree_sum[pos]+=val;
36 pos+=lb(pos);
37 }
38 }
39 inline LL Interval_Ask(LL pos,bool how)
40 {
41 LL ans=0;
42 while(pos)
43 {
44 if(how==1) ans=ans+tree_num[pos];
45 else ans=ans+tree_sum[pos];
46 pos-=lb(pos);
47 }
48 return ans;
49 }
50 int main()
51 {
52 n=read();
53 for(LL i=1;i<=n;i++) cow[i].v=read(),cow[i].x=read(),MAXX=max(MAXX,cow[i].x);
54 sort(cow+1,cow+n+1,comp);
55 LL ans=0;
56 for(LL i=1;i<=n;i++)
57 {
58 // 1:数量 0:和
59 ans+=cow[i].v*( ( -cow[i].x*( Interval_Ask(MAXX,1)-Interval_Ask(cow[i].x,1) ) + (Interval_Ask(MAXX,0)-Interval_Ask(cow[i].x,0)) )+
60 cow[i].x*Interval_Ask(cow[i].x,1)-(Interval_Ask(cow[i].x,0)) );
61 Point_Add(cow[i].x,1,1);
62 Point_Add(cow[i].x,cow[i].x,0);
63 }
64 printf("%lld",ans);
65 return 0;
66 }