首页 > 代码库 > POJ1990 MooFest

POJ1990 MooFest

题解:

将耳背程度排序,那么对于每次新增一头牛时,只需要算出有前面有多少头牛的距离x比它小以及总和,还有多少头牛的距离x比它大以及总和,就可以计算了。

用2个树状数组维护

一个维护和,一个维护数目

代码:

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=20010;const int mod=1e9+7;const int INF=1e9;pair<LL,LL> p[maxn];int n;LL a,b;LL Sum[maxn];LL e[maxn],d[maxn];int lowbit(int x){return x&-x;}void add(int x,LL v,LL* c){    while(x){        c[x]+=v;        x-=lowbit(x);    }}LL sum(int x,LL* c){    LL cnt=0;    while(x<maxn){        cnt+=c[x];        x+=lowbit(x);    }    return cnt;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].fs,&p[i].se);    sort(p+1,p+n+1);    for(int i=1;i<=n;i++) Sum[i]=Sum[i-1]+p[i].se;    LL ans=0;    add(p[1].se,p[1].se,e);    add(p[1].se,1LL,d);    for(int i=2;i<=n;i++){        LL tmp=sum(p[i].se,e);//>=p[i].se        LL num=sum(p[i].se,d);        ans+=((i-1-num)*p[i].se-(Sum[i-1]-tmp)+tmp-num*p[i].se)*p[i].fs;        add(p[i].se,p[i].se,e);        add(p[i].se,1LL,d);        //cout<<ans<<endl;    }    printf("%lld\n",ans);    return 0;}

 

POJ1990 MooFest