P2345 奶牛集会/P2657 低头一族

luogu 传送门 双倍经验！
树状数组题
v[i]只有当和比它小的v[j]一起运算时才对答案有贡献。
我们可以这样来处理，离线来做。将所有奶牛按照v升序排序，然后一个奶牛一个奶牛的查询，再插入。
我们要树状数组来维护一个数组cnt[i]，和sum[i]表示i-lowbit(i) ~ i范围内数的个数和这些数的和。
我们查询时，记num1为前i-1头奶牛中小于x[i]的头数，num2为大于等于x[i]的头数（num2=i-1-num1），s1为1~x[i]范围内数的和收，tot为前i-1头奶牛x[]之和，s2=tot-s1。那么每头奶牛对答案的贡献是v[i]*（num1*xi-s1+s2-num2*xi）//去掉绝对值符号嘛。

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> #define LL long long #define M 100005 using namespace std; int n; struct H{LL x,v; }st[M]; LL cnt[20009],sum[20009]; LL ans,num,s,maxn,tot; bool cmp(H a,H b){return a.v<b.v;} void ask(int x) {for(int i=x;i>=1;i-=i&(-i))num+=cnt[i],s+=sum[i]; } void add(int x) {for(int i=x;i<=maxn;i+=i&(-i))cnt[i]+=1,sum[i]+=x; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld",&st[i].v,&st[i].x),maxn=max(maxn,st[i].x);sort(st+1,st+n+1,cmp);for(int i=1;i<=n;i++){num=0,s=0;ask(st[i].x);ans+=st[i].v*(2*num*st[i].x+tot-2*s-(i-1)*st[i].x);tot+=st[i].x;add(st[i].x); }printf("%lld",ans);return 0; }

转载于:https://www.cnblogs.com/dfsac/p/7587835.html

总结

以上是生活随笔为你收集整理的P2345 奶牛集会/P2657 低头一族的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。