POJ 1990 线段树

题意：

思路：

线段树 （一棵就够啦 不像树状数组，还得用两棵）

先对v从小到大排序。每回插入的时候当前的v是最大的，只需要统计它到各个坐标的距离就好了。

里面存两个东西：

这个坐标左边的坐标个数和这个坐标左边的坐标之和。

ans_num表示这个坐标左边的坐标个数

ans_num表示这个坐标左边的坐标之和

tot_sum表示一共的坐标之和

i表示当前处理的是第i头牛

ans+=(cow[i].pos*ans_num-ans_sum+tot_sum-cow[i].pos*(i-ans_num-1)-ans_sum)*cow[i].v;

最后说一句：要用long long。。。。。

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

#define int long long

int n,xx,ans_num,ans_sum,tot_sum,ans=0;

struct Cow{int pos,v;}cow[22222];

struct Tree{int num,sum;}tree[88888];

bool cmp(Cow a,Cow b){return a.v<b.v;}

void insert(int l,int r,int pos){

    if(l==r){

        tree[pos].num++;

        tree[pos].sum+=xx;

        return;

    }

    int mid=(l+r)>>1;

    if(mid>=xx)insert(l,mid,pos<<1);

    else insert(mid+1,r,pos<<1|1);

    tree[pos].num=tree[pos<<1].num+tree[pos<<1|1].num;

    tree[pos].sum=tree[pos<<1].sum+tree[pos<<1|1].sum;

}

void query(int l,int r,int pos){

    if(r<xx){

        ans_num+=tree[pos].num;

        ans_sum+=tree[pos].sum;

        return;

    }

    int mid=(l+r)>>1;

    if(mid>=xx-1)query(l,mid,pos<<1);

    else query(l,mid,pos<<1),query(mid+1,r,pos<<1|1);

}

signed main(){

    scanf("%lld",&n);

    for(int i=1;i<=n;i++)

        scanf("%lld%lld",&cow[i].v,&cow[i].pos);

    sort(cow+1,cow+1+n,cmp);

    for(int i=1;i<=n;i++){

        xx=cow[i].pos;

        ans_num=ans_sum=0;

        query(0,20000,1);

        insert(0,20000,1);

        ans+=(xx*ans_num-ans_sum+tot_sum-xx*(i-ans_num-1)-ans_sum)*cow[i].v;

        tot_sum+=cow[i].pos;

    }

    printf("%lld\n",ans);

}