Description Every year, Farmer John’s N (1 <= N <= 20,000) cows attend
“MooFest”,a social gathering of cows from around the world. MooFest
involves a variety of events including haybale stacking, fence
jumping, pin the tail on the farmer, and of course, mooing. When the
cows all stand in line for a particular event, they moo so loudly that
the roar is practically deafening. After participating in this event
year after year, some of the cows have in fact lost a bit of their
hearing.Each cow i has an associated “hearing” threshold v(i) (in the range
1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by
cow i. If two cows i and j wish to converse, they must speak at a
volume level equal to the distance between them times max(v(i),v(j)).Suppose each of the N cows is standing in a straight line (each cow at
some unique x coordinate in the range 1..20,000), and every pair of
cows is carrying on a conversation using the smallest possible volume.Compute the sum of all the volumes produced by all N(N-1)/2 pairs of
mooing cows.Input
* Line 1: A single integer, N
- Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the
second cow; and so on. No two cows will stand at the same location.Output
* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows.
对于每个牛，只统计声音小于（等于）他的，这样就可以直接累计。
按声音从小到大排序，对于每头牛只要计算与目前所有加入的牛的距离和就行了。
当有n头牛在左边时，sum=x-x1+x-x2+…+x-xn=n * x- Σx(1..n)
在右边的同理。
所以发现，只要用树状数组维护区间的坐标和、个数和即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int maxm=20000;
struct cow
{int v,p;bool operator < (const cow & cc) const{return v<cc.v;}
}a[20010];
LL s[20010],t[20010];
int n;
LL qry_s(int k)
{LL ret=0;for (;k;k-=k&-k)ret+=s[k];return ret;
}
LL qry_t(int k)
{LL ret=0;for (;k;k-=k&-k)ret+=t[k];return ret;
}
void add_s(int k,int x)
{for (;k<=maxm;k+=k&-k)s[k]+=x;
}
void add_t(int k)
{for (;k<=maxm;k+=k&-k)t[k]++;
}
int main()
{int i,j,k,p,q;LL x,y,z,sum=0,ans=0;scanf("%d",&n);for (i=1;i<=n;i++)scanf("%d%d",&a[i].v,&a[i].p);sort(a+1,a+n+1);for (i=1;i<=n;i++){x=qry_s(a[i].p);y=qry_t(a[i].p);ans+=a[i].v*(y*a[i].p-x+sum-x-(i-y-1)*a[i].p);add_s(a[i].p,a[i].p);add_t(a[i].p);sum+=a[i].p;}printf("%lld\n",ans);
}