有$n$个牛每个牛有听力$v$和位置$x$，对于每个牛对$(i,j)$能产生$max(v_i,v_j)\cdot |x_i-x_j|$求所有牛对的能量和
首先应该想到是一个统计题，那$max$就有点难处理，不妨给定一个顺序把牛按听力排序，这样一边遍历一边处理
现在假设已经考虑到$i$，前面都是听力比$i$小的，那么距离和如何统计呢？我们可以做一个分类，距离比$i$小的和距离比$i$大的
对于距离比$i$小的，我们求出距离比$i$小的个数$t$，这$t$个牛距离和为$sum_1$，那么对答案就能产生$t\cdot x_i-sum$的贡献，把这个贡献设为$ans_1$
对于距离比$i$大的，我们把目前所有的距离和$sum$减去小于$x$的距离和，那么对答案产生的贡献就是$sum-sum_1-(i-t-1)\cdot x_i$，这两个贡献加起来乘以$v_i$即可
然后每次统计完一个的贡献以后，就把当前距离加进考虑范围，由于两个查询都是查询前缀和，并且是单点修改，所以我们可以用两个树状数组来维护，两个下标都是坐标，一个维护比当前坐标小的牛的个数，另一个维护比当前坐标小的牛的距离的和即可
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
|
const int maxn=20050;
const int N=20000;
ll n,c1[maxn],c2[maxn];
struct node{
ll v,x;
bool operator<(const node&t) const{
return v<t.v;
}
}a[maxn];
int lowbit(int x){return x&-x;}
void add1(int x,int p)
{
while(x<=N)
{
c1[x]+=p;
x+=lowbit(x);
}
}
void add2(int x,int p)
{
while(x<=N)
{
c2[x]+=p;
x+=lowbit(x);
}
}
ll query1(int x)
{
ll res=0;
while(x)
{
res+=c1[x];
x-=lowbit(x);
}
return res;
}
ll query2(int x)
{
ll res=0;
while(x)
{
res+=c2[x];
x-=lowbit(x);
}
return res;
}
int main()
{
cin>>n;
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(int i=1;i<=n;i++) read(a[i].v),read(a[i].x);
sort(a+1,a+n+1);
ll ans=0,sum=0;
for(int i=1;i<=n;i++)
{
ll t=query1(a[i].x);
ans+=(a[i].x*t-query2(a[i].x))*a[i].v;
ans+=(sum-query2(a[i].x)-(i-t-1)*a[i].x)*a[i].v;
sum+=a[i].x;
add1(a[i].x,1);
add2(a[i].x,a[i].x);
}
cout<<ans<<endl;
return 0;
}
|