如题，题目P2345

朴素 O（n2）算法大概跑出来1s

我的疑似 O（nlogn）算法高达 400 ms

然而最快的都有 40ms 了 。。。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ull;
ull n,ans,sum[21000];
struct animal
{
	ull v,x;
}p[21000];
bool cmp1(animal u1,animal u2)
{
	if(u1.v!=u2.v) return u1.v<u2.v;
	return u1.x<u2.x; 
}
bool cmp2(animal u1,animal u2)
{
	return u1.x<u2.x;
}
void work(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	work(l,mid);
	work(mid+1,r);
	
	memset(sum,0,sizeof(sum));
	
	ull h1=l-1,h2=mid;
	ull t=0;
	for(int i=l;i<=mid;i++)
	t+=p[i].x;

	while(h2<r)
	{
		h2++;
		while(p[h1+1].x<p[h2].x&&h1<mid) h1++,t=t-p[h1].x*2;
  
		ans=ans+p[h2].v*((h1*2-mid-l+1)*p[h2].x+t);
	}
	sort(p+l,p+r+1,cmp2);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i].v>>p[i].x;
	sort(p+1,p+n+1,cmp1);
	work(1,n);
	cout<<ans;
}