这个题最重要的一点就是每个点分别左右扫，只扫比它v（i）小的牛，那么最终就可以每两只必说一次话，用树状数组加上排序，进行条件控制，很神奇，看来我还太菜
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=20000+100; int num[maxn],distan[maxn]; typedef long long ll; struct note { int w,x; bool operator <(const note &p) { return x<p.x; } }a[maxn]; int n; ll sum(int *aa,int x) { ll sum=0; for(int i=x;i>0;i-=i&-i) sum+=aa[i]; return sum; } void add(int x,int *aa,int v) { for(int i=x;i<=maxn-100;i+=i&-i) aa[i]+=v; } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].x); sort(a+1,a+n+1);//按照x从大到小排序，也就是位置从左往右排序 memset(num,0,sizeof(num)); memset(distan,0,sizeof(distan)); ll ans=0; for(int i=1;i<=n;i++)//寻找在位置在i左边而且w小于i的牛 { int w=a[i].w,x=a[i].x; ll prenum=sum(num,w-1); ll predis=sum(distan,w-1); ans+=(prenum*x-predis)*w; add(w,num,1); add(w,distan,x); } memset(num,0,sizeof(num)); memset(distan,0,sizeof(distan)); for(int i=n;i>=1;i--)//寻找在位置在i右边而且w小于i的牛 { int w=a[i].w,x=a[i].x; ll prenum=sum(num,w); ll predis=sum(distan,w); ans+=(predis-prenum*x)*w; add(w,num,1); add(w,distan,x); } printf("%lld\n",ans); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7272650.html
