树状数组和线段树的解法比较，感觉不论在内存还是时间上都是树状数组占优
大题思路对 v从小到大进行排序，之后找之前的（也就是比v小的坐标）
v * sum（abs（xi – x）） 这样的话 abs无法处理，我们用另外一个树状数组记录在x ~ y区间牛的个数，之前那个记录在x ~ y区间内牛的坐标和
Accepted
48479
C++
1131
树状数组代码：
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;typedef long long LL;const int maxn = 22222;int C1[maxn],C2[maxn];int n = 20005,nn;struct Cow{int v,x;friend bool operator < (Cow p,Cow q){return p.v < q.v;}}cow[maxn];int lowbit(int x){return x & -x;}int sum(int C[],int x){int ret = 0;while(x > 0){ret += C[x];x -= lowbit(x);}return ret;}void add(int C[],int x,int d){while(x <= n){C[x] += d;x += lowbit(x);}}int main(){scanf("%d",&nn);memset(C1,0,sizeof(C1));memset(C2,0,sizeof(C2));for(int i = 0; i < nn; i++)scanf("%d%d",&cow[i].v,&cow[i].x);sort(cow,cow + nn);LL ans = 0;for(int i = 0; i < nn; i++){int x = cow[i].x,v = cow[i].v;int m1 = sum(C1,x),n1 = sum(C2,x);int m2 = sum(C1,n) – m1,n2 = sum(C2,n) – n1;ans += (((LL)n1 * x – m1) + ((LL)m2 – n2 * x)) * v;add(C1,x,x);add(C2,x,1);}printf("%I64d\n",ans);return 0;}
Accepted
932110
C++
1723
线段树代码：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 20005;typedef long long LL;/*线段树解法*/#define lson (pos<<1)#define rson (pos<<1|1)int v1[maxn << 2],v2[maxn << 2];struct Node{int x,v;friend bool operator < (Node p,Node q){return p.v < q.v;}}node[maxn];void build(){memset(v1,0,sizeof(v1));memset(v2,0,sizeof(v2));}void pushup(int v[],int pos){v[pos] = v[lson] + v[rson];}void update(int v[],int L,int R,int aim,int pos,int value){if(L == R){v[pos] += value;return;}int mid = (L + R) >> 1;if(aim <= mid)update(v,L,mid,aim,lson,value);elseupdate(v,mid + 1,R,aim,rson,value);pushup(v,pos);}int query(int v[],int L,int R,int l,int r,int pos){if(l <= L && R <= r){return v[pos];}int mid = (L + R) >> 1;int ans = 0;if(l <= mid)ans += query(v,L,mid,l,r,lson);if(r > mid)ans += query(v,mid + 1,R,l,r,rson);return ans;}int main(){build();int n,max_size = 0;scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d%d",&node[i].v,&node[i].x);max_size = max(max_size,node[i].x) + 1;}sort(node,node + n);LL ans = 0;for(int i = 0; i < n; i++){int x = node[i].x,v = node[i].v;ans += ((LL)(x * query(v2,1,max_size,1,x,1)) – (LL)(query(v1,1,max_size,1,x,1))) * v;ans += ((LL)(query(v1,1,max_size,x,max_size,1)) – (LL)(query(v2,1,max_size,x,max_size,1) * x)) * v;//printf("%d %I64d\n",i,ans);update(v2,1,max_size,x,1,1);update(v1,1,max_size,x,1,x);}printf("%I64d\n",ans);return 0;}
，泪，一种痛苦的雨滴，不知从什么时候开始已在我的世界下个不停。
