USACO 2004 OPEN Moofest(一)

　　先按照坐标x进行排序，随后用归并排序对v进行排序。用部分和去求总和。

　　#include

　　#include

　　const int maxn=20002;

　　int v[maxn],x[maxn],n;

　　int b[maxn],c[maxn];

　　long long int ans;

　　void swap(int *a,int *b)

　　{

　　int tmp=*a;

　　*a=*b;

　　*b=tmp;

　　}

　　void sort(int l,int r)

　　{

　　int key=x[rand()%(r-l+1)+l];

　　int i=l,j=r;

　　while(i<=j)

　　{

　　while(x[i]>key)

　　i++;

　　while(x[j]

　　j--;

　　if(i<=j)

　　{

　　swap(&x[i],&x[j]);

　　swap(&v[i],&v[j]);

　　i++;

　　j--;

　　}

　　}

　　if(l

　　sort(l,j);

　　if(i

　　sort(i,r);

　　}

　　void merge_sort(int l,int r)

　　{

　　if(l==r)

　　return;

　　int mid=(l+r)/2;

　　merge_sort(l,mid);

　　merge_sort(mid+1,r);

　　int p1=l,p2=mid+1;

　　int i=l;

　　long long int sum1=0,sum2=0;

　　for(int i=p1;i<=mid;i++)

　　{

　　sum1+=v[i];

　　}

　　for(int i=p2;i<=r;i++)

　　{

　　sum2+=v[i];

　　}

　　while(p1<=mid || p2<=r)

　　{

　　if((p2>r)||(p1<=mid&&v[p1]>v[p2]))

　　{

　　ans += v[p1] * ((r-p2+1)*x[p1] - sum2);

　　sum1-=v[p1];

　　c[i]=x[p1];

　　b[i++]=v[p1++];

　　}

　　else

　　{

　　ans+=v[p2]*((mid-p1+1)*x[p2]-sum1);

　　sum2-=v[p2];

　　c[i]=x[p2];

　　b[i++]=v[p2++];

　　}

　　}

　　for(int i=l;i<=r;i++)

　　{

　　x[i]=c[i];

　　v[i]=b[i];

　　}

　　}