Disharmony Trees

/*错误思路：按照高度排好序之后整个的求值过程就变成了h[1]*abs((n*a[1]-(a[2]+a[3]+..+a[n])))+h[2]*abs(((n-1)*a[2]-(a[3]+a[4]+..+a[n])))+.....然后用树状数组维护a序列的值解析：因为绝对值的问题所以(n*a[1]-(a[2]+a[3]+..+a[n]))这个位置不能直接减去，要考虑大小才能把括号去掉正确思路：按照高排好序之后，每棵树的min_h肯定是本身的h，abs_a的话需要考虑从i到n的a与本身的大小树状数组维护两个值比自己小的有多少个，还有维护a数组，*/#include<bits/stdc++.h>#define N 100005#define ll long long#define lowbit(x) x&(-x)using namespace std;struct node{    ll x,h;    ll rankx,rankh;    node(){}    node(ll a,ll b)    {        x=a;        h=b;    }};ll n;ll x,h;ll c[N];//用来构建树状数组维护到当前结点比当前结点小的个数ll sum[N];//用来维护到当前结点比当前结点小的数的总和node f[N];bool cmp1(node a,node b){    return a.x<b.x;}bool cmp2(node a,node b){    return a.h<b.h;}bool cmp3(node a,node b)//这次排序从大到小排序，这样能使从0到i的所有计算中用到的h都是h[i];{    return a.h>b.h;}void init(){    memset(c,0,sizeof c);    memset(sum,0,sizeof sum);}void update1(ll x,ll val){    while(x<N)    {        c[x]+=val;        x+=lowbit(x);    }}void update2(ll x,ll val){    while(x<N)    {        sum[x]+=val;        x+=lowbit(x);    }}ll getsum1(ll x)//这个是获取有多少个比自己小的{    ll s=0;    while(x>0)    {        s+=c[x];        x-=lowbit(x);    }    return s;}ll getsum2(ll x)//这个是获取比自己小的和{    ll s=0;    while(x>0)    {        s+=sum[x];        x-=lowbit(x);    }    return s;}int main(){    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);    while(scanf("%lld",&n)!=EOF)    {        init();        f[0]=node(-1,-1);        for(int i=1;i<=n;i++)        {            scanf("%lld%lld",&x,&h);            f[i]=node(x,h);        }//处理输入        sort(f+1,f+n+1,cmp1);//先按照坐标的大小进行排序        for(int i=1;i<=n;i++)        {            if(f[i].x==f[i-1].x)                f[i].rankx=f[i-1].rankx;            else                f[i].rankx=i;        }        sort(f+1,f+n+1,cmp2);//然后按照树的高度的大小进行排序        for(int i=1;i<=n;i++)        {            if(f[i].h==f[i-1].h)                f[i].rankh=f[i-1].rankh;            else                f[i].rankh=i;        }        sort(f+1,f+n+1,cmp3);//第三次排序保证每次运算用到的h都是h[i](也就是使得h[i]在0到i中最小;        ll cur=0;        ll total=0;        ll same=0;//和自己相同的个数        ll low=0;//比自己小的个数        ll big=0;//比自己大的个数        ll low_sum=0;//比自己小的和        ll big_sum=0;//比自己大的和        //for(int i=1;i<=n;i++)        //    cout<<f[i].rankx<<" ";        //cout<<endl;        for(int i=1;i<=n;i++)        {            total+=f[i].rankx;//表示到当前位置的总坐标值            /*更新当前的信息*/            update1(f[i].rankx,1);            update2(f[i].rankx,f[i].rankx);            //和当前位置相同的个数            same=getsum1(f[i].rankh)-getsum1(f[i].rankh-1);            //比自己小的个数;            low=getsum1(f[i].rankx-1);            //比自己大的个数            big=i-same-low;            //比自己小的和            low_sum=getsum2(f[i].rankx-1);            //比自己大的和            big_sum=total-low_sum-same*f[i].rankx;            //cout<<"total           ="<<total<<endl;            //cout<<"getsum1(x)      ="<<getsum1(x)<<endl;            //cout<<"i-getsum1(x)-1  ="<<i-getsum1(x)-1<<endl;            //cout<<"getsum2(x)      ="<<getsum2(x)<<endl;            //cout<<"total-getsum2(x)="<<total-getsum2(x)<<endl;            //cout<<endl;                                               //比自己大的和减去比当前值大的和            cur+=f[i].rankh*((low*f[i].rankx-low_sum)+(big_sum-big*f[i].rankx));                        //a[i]乘上比自己小的个数减去比自己小的和        }        printf("%lld\n",cur);    }    return 0;}