View Code of Problem 1075

/**树状数组**/
/**
题意：FJ有n头牛，排列成一条直线(不会在同一个点)，给出每头牛在直线上的坐标x。
另外，每头牛还有一个自己的声调v，如果两头牛(i和j)之间想要沟通的话，它们必须用同个音调max(v[i],v[j])，
沟通起来消耗的能量为：max(v[i],v[j]) * 它们之间的距离。问要使所有的牛之间都能沟通(两两之间)，
总共需要消耗多少能量。

思路:
用c[i]表示第i头牛,
     将原来的牛按坐标从小到大排序,这样就不用考虑绝对值了,再按顺序依次添加到树状数组。用声调作为树状数组的下标，
     每次添加时,
     需要知道当前这头牛声调c[i].w之前有多少头牛,用N表示，这些牛与0点的距离的和X，以及当前这头牛离0点的距离c[i].x，
     这样,ans+=c[i].w*(N*c[i].x-X),i=0 ~ n-1.
     因此,要用两个树状数组,sum[x]作为声调1~x之间有多少头牛,sum[x]是指这些牛与0点距离的总和,每算一次ans,就再添加一头牛.
     
     但是,上面的计算只是每头牛和这头牛位置之前,且声调小于当前牛的牛沟通了……
     每头牛和这头牛位置之后,且声调小于当前牛的牛没有进行沟通.............
     因此,
     需要从n-1头牛开始,向前再做一边上面的过程,只是ans+=c[i].w*(X-N*c[i].x),i= n-1 ~ 0
     但两次进行同一过程,会将声调相同的两头牛的消耗多计算一次,因此，如代码般调整即可~~~~ 
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include<algorithm>

using namespace std;
#define maxn 20000             //题目给的范围
#define lowbit(x) (x)&(-x)
typedef long long ll;
struct Cow
{
    int v,x;
}c[maxn+10];

int n;
ll num[maxn+10];
ll sumx[maxn+10];//注意,题目给的距离之和可能上亿,int是不够的,全部换成long long

bool cmp(Cow a,Cow b)
{
    return a.x<b.x;
}
void init(int add,int x,ll a[])//树状数组插入数据
{
    while(x<=maxn)
    {
        a[x]+=add;
        x+=lowbit(x);
    }
}

ll query(int x,ll a[])//树状数组查询
{
    ll ans=0;
    while(x>0)
    {
        ans+=a[x];
        x-=lowbit(x);
    }
    return ans;
}

void read()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&c[i].v,&c[i].x);
    sort(c,c+n,cmp);
}

void deal()
{
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        ll N=query(c[i].v-1,num);//只要v-1情况,不包括v,即不包括声调相同的
        ll X=query(c[i].v-1,sumx);
        ans+=(N*c[i].x-X)*c[i].v;
        init(c[i].x,c[i].v,sumx);
        init(1,c[i].v,num);
    }
    memset(num,0,sizeof(num));
    memset(sumx,0,sizeof(sumx));
    for(int i=n-1;i>=0;i--)
    {
        ll N=query(c[i].v,num);//这次就包括声调相同的
        ll X=query(c[i].v,sumx);
        ans+=(X-N*c[i].x)*c[i].v;
        init(c[i].x,c[i].v,sumx);
        init(1,c[i].v,num);
    }
    printf("%lld\n",ans);
}

int main()
{
    read();
    deal();
    return 0;
}