POJ 1990 MooFest | 树状数组

题面:

给出一群牛,每个牛牛有一个坐标和val,每两对牛牛之间的w被定义为

dis(x[i],x[j])*max(val[i],val[j])

求w的和

题解:

我们如果按val排序,对于i来说,和他构成的权值乘的是val[i]的显然是1~i-1的牛牛

设有a个牛在他前面,b个牛在他后面

公式变成val[i]*(a*x[i]-前面牛的距离和+后面牛的距离和-b*x[i])

接下来考虑维护一下他和其他牛牛的距离,可以用树状数组记录一下,给每个坐标赋一个大小为坐标的权值

这样用树状数组就维护可以这个点之前有多少dis,这个点之后有多少dis,
顺便维护一下前后多少牛即可

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define N 20100
 5 typedef long long ll;
 6 using namespace std;
 7 struct cow
 8 {
 9     ll x,val;
10     bool operator < (const cow &a) const
11     {
12         return val<a.val;
13     }
14 }c[N];
15 ll n,maxx,ans;
16 struct BIT
17 {
18     ll t[N],lim;
19     void modify(ll x,ll k)
20     {
21         while (x<=lim)
22         t[x]+=k,x+=x&-x;
23     }
24     ll query(ll x)
25     {
26         ll ret=0;
27         while (x>0)
28         ret+=t[x],x-=x&-x;
29         return ret;
30     }
31 }dis,cnt;
32 int main()
33 {
34     scanf("%lld",&n);
35     for (int i=1;i<=n;i++)
36     scanf("%lld%lld",&c[i].val,&c[i].x),maxx=max(maxx,c[i].x);
37     sort(c+1,c+1+n);
38     dis.lim=maxx,cnt.lim=maxx;
39     for (int i=1;i<=n;i++)
40     {
41     ll tmp=cnt.query(c[i].x);
42     ans+=c[i].val*(tmp*c[i].x-dis.query(c[i].x));
43     tmp=cnt.query(maxx)-cnt.query(c[i].x);
44     ans+=c[i].val*(dis.query(maxx)-dis.query(c[i].x)-tmp*c[i].x);
45     cnt.modify(c[i].x,1);
46     dis.modify(c[i].x,c[i].x);
47     }
48     printf("%lld",ans);
49     return 0;
50 }