题解 P2345 【奶牛集会】
YoungNeal
2018-07-18 21:40:48
## Solution
看到楼下大佬们的log级数据结构表示并不会，我只会暴力数据结构，于是我用分块过了这题。
首先将所有奶牛按照坐标升序排序，并假设我们已经求出每个奶牛到前面所有奶牛的距离和存进了qzh数组。
考虑这个性质：当前扫到了奶牛i，那么奶牛i的贡献至少是$v[i]\times qzh[i]$，称这个为基础贡献。
所以我们不妨对所有奶牛先求出基础贡献，然后再在之后扫描一遍用奶牛i前面的v值比它大的奶牛j来更新一下答案，设答案为ans，也就是 $ans+=(v[j]-v[i])\times (x[i]-x[j])$ 。
展开这个式子， $v[j]\times x[i]-v[j]\times x[j]-v[i]\times x[i]+v[i]\times x[j]$。
发现这几项都可以用前缀和维护，就做完了。
用分块只是为了平衡一下时间复杂度
## Code
```cpp
#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define N 20005
#define int long long
#define min(A,B) ((A)<(B)?(A):(B))
#define max(A,B) ((A)>(B)?(A):(B))
#define swap(A,B) ((A)^=(B)^=(A)^=(B))
int n,ans;
int qzh[N];
int belong[N];
int block,l[N],r[N];
int vx[204][N],v[204][N],x[204][N];
struct Node{
int a,b;
}node[N];
bool cmp(Node x,Node y){
return x.a<y.a;
}
bool cmp2(Node x,Node y){
return x.b<y.b;
}
int getint(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void write(int x){
if(x>9) write(x/10);
putchar(x%10+'0');
}
void init(int y){
std::sort(node+l[y],node+r[y]+1,cmp2);
vx[y][l[y]]=node[l[y]].a*node[l[y]].b;
v[y][l[y]]=node[l[y]].b;
x[y][l[y]]=node[l[y]].a;
for(int i=l[y]+1;i<=r[y];i++){
vx[y][i]=vx[y][i-1]+node[i].a*node[i].b;
v[y][i]=v[y][i-1]+node[i].b;
x[y][i]=x[y][i-1]+node[i].a;
}
}
int bsearch(int l,int r,int p){
int ans=0;
while(l<=r){
int mid=l+r>>1;
if(node[mid].b>p)
ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
signed main(){
n=getint();
block=sqrt(n);
for(int i=1;i<=n;i++){
belong[i]=(i-1)/block+1;
node[i].b=getint();
node[i].a=getint();
}
int tot=n/block+(n%block?1:0);
for(int i=1;i<=tot;i++){
l[i]=(i-1)*block+1;
r[i]=i*block;
} r[belong[n]]=n;
std::sort(node+1,node+1+n,cmp);
for(int i=2;i<=n;i++)
qzh[i]=qzh[i-1]+(node[i].a-node[i-1].a)*(i-1),ans+=node[i].b*qzh[i];
for(int i=2;i<=n;i++){
if(belong[i]!=belong[i-1])
init(belong[i-1]);
for(int j=1;j<belong[i];j++){
int p=bsearch(l[j],r[j],node[i].b);
if(!p) continue; p--;
int q=node[i].a*(v[j][r[j]]-v[j][p])-vx[j][r[j]]+vx[j][p]+node[i].b*(x[j][r[j]]-x[j][p])-(r[j]-p)*node[i].a*node[i].b;
ans+=q;
}
for(int j=l[belong[i]];j<i;j++){
if(node[j].b>node[i].b)
ans+=node[i].a*node[j].b-node[j].b*node[j].a+node[i].b*node[j].a-node[i].a*node[i].b;
}
}
printf("%lld\n",ans);
return 0;
}
```