首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。