题解 P2345 【奶牛集会】
由于不会用洛谷的表格，所以之前写的题解看起来比较呲毛，在即将退役之际，用图床优化了一下外观。。。（真的退役了，闭关虽云乐，不如早早滚回去学文化课。。。）
这道题，如果考虑暴力的话，肯定会炸...
只能对公式max{Vi; Vj}×|Xi − Xj |进行优化
对于max，很容易想到sort将vi从小到大排序。。。
然后，优化绝对值的漫漫征程就此开始...
先研究一下样例 （sort后）
我们建立一个坐标轴，安置一下各位奶牛
先把第一头放进去
此时他周围没有牛，不发声
接着是第二头
2号牛前面有一头牛，于是发出声音2*（6-5）
然后是第三头...
在3号后面有两头牛，发出声音3（5-1+6-1）也就是3（5+6-1*2）（但愿你会想到什么）
最后是第四头
4号前有一头牛，后有两头牛，于是发出声音3（3-1）+3（5+6-3*2）
样例讲完了...
这时思路就出来了，我们把牛一头又一头地放入坐标系，每次放进去都算一次他与其他所有放进去的牛的声音，最后把每次放入求出的值加起来就是答案
或许你会发现，第i头牛和其他的牛发出的声音就等于=第i头牛的vi（它之前牛的数目它的坐标-它之前所有牛的坐标和）+vi（它之后所有牛的坐标和-它之后牛的数目他的坐标），对于牛的数目和牛的坐标，我们都可以用树状数组来维护一下...
如果你不明白为什么树状数组能维护，那我就拿牛的坐标来举一个例子...
以样例为例，开一个和坐标轴等长的树状数组，加入1号（插入位置为1号的横坐标，值为1），此时sum[maxx]=1,加入2号，sum[maxx]=2,二号之前于是有sum[5]头牛，之后有sum[maxx]-sum[6]头牛，加入三号，它之前有sun[0]头牛，之后有sum[maxx]-sum[1]头牛，以此类推...
一定开long long ！！！
切记切记
代码如下
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long wz[20010],yy[20010],n,mn=20000;
long long ans;
long long read()
{
long long xx=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
xx=xx*10+ch-'0';
ch=getchar();
}
return xx;
}
struct node{
long long xi;
long long vi;
}a[20010];
bool cmp(node x,node y)
{
return x.vi<y.vi;
}
int lobit(int x) { return x&(-x);}
void crwz(int x) { for(;x<=mn;x+=lobit(x)) wz[x]++;}
int z(int x)
{
int sum=0;
for(;x>=1;x-=lobit(x)) sum+=wz[x];
return sum;
}
void cryy(int x,int v) { for(;x<=mn;x+=lobit(x)) yy[x]+=v;}
int y(int x)
{
int sum=0;
for(;x>=1;x-=lobit(x)) sum+=yy[x];
return sum;
}
int jdz(int x)
{
if(x<0) return -x;
else return x;
}
int main()
{
n=read();
for(int i=1;i<=n;++i) a[i].vi=read(),a[i].xi=read();
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i)
{
int j=a[i].xi;
ans+=a[i].vi*(z(j-1)*j-y(j-1)+y(mn)-y(j)-(z(mn)-z(j))*j);
crwz(a[i].xi);
cryy(j,a[i].xi);
}
printf("%lld",ans);
return 0;
}谢谢观看！！！