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 低头一族的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。