【POJ】1990-MooFest（树状数组or线段树）

树状数组和线段树的解法比较，感觉不论在内存还是时间上都是树状数组占优

大题思路对 v从小到大进行排序，之后找之前的（也就是比v小的坐标）

v * sum（abs（xi - x）） 这样的话 abs无法处理，我们用另外一个树状数组记录在x ~ y区间牛的个数，之前那个记录在x ~ y区间内牛的坐标和

树状数组代码：

#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;
}

线段树代码：

#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);
    else
        update(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;
}