[Usaco2004 Open]MooFest 狂欢节

Description

有n个奶牛,给出每个奶牛的
对于每一对奶牛之间的交流音量为,求所有奶牛之间音量总和

Solvution

考虑到不好处理,那么我们就按从小到大排序,那么对于第个奶牛对于答案的贡献就是考虑到绝对值还是不好处理,那么我们把它转化为两部分


然后我们用前缀和维护一下
用树状数组维护一下的个数
然后最后的答案就是

复杂度是

Code

#include <cstdio>
#include <ctype.h>
#include <cstdlib>

#include <algorithm>

template <typename T>inline T read(T &f) {
    f = 0;
    int x = 1;
    char c = getchar();
    while(!isdigit(c)) { if(c == '-') x = -1 ; c = getchar(); }
    while(isdigit(c)) f = (f << 1) + (f << 3) + c - '0' , c = getchar();
    return f = f * x;
}

#define LL long long
#define lowbit(x) (x & -x)

const int maxn = 20000 + 5;

struct Node{
    LL v , x;
    bool operator <(const Node &B)const{
        return v < B.v;
    }
}A[maxn];

int n;

LL S[maxn] , Bit[maxn] , Bit_cnt[maxn];
LL Ans , L , R;

void add(LL x){
    LL res = x;
    while(x < maxn){
        Bit[x] += res;
        Bit_cnt[x] += 1;
        x += lowbit(x);
    }
}
void sum(LL x,LL &res,LL &temp){
    res = temp = 0;
    while(x){
        res += Bit[x];
        temp += Bit_cnt[x];
        x -= lowbit(x);
    }
}

int main(){
    read(n);
    for(int i = 1 ; i <= n ; i++ ) read(A[i].v) , read(A[i].x);
    std::sort(A + 1,A + 1 + n);
    for(int i = 1 ; i <= n ; i++ ) {
        add(A[i].x);
        sum(A[i].x - 1,L,R);
        Ans = Ans + A[i].v * (S[i - 1] - L - (i - R - 1) * A[i].x);
        Ans = Ans + A[i].v * (R * A[i].x - L);
        S[i] = S[i - 1] + A[i].x;
    }
    printf("%lld\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注