首页 > 代码库 > POJ 1990 MooFest（zkw线段树）
POJ 1990 MooFest（zkw线段树）
【题目链接】 http://poj.org/problem?id=1990
【题目大意】
给出每头奶牛的位置和至少要多少分贝的音量才能听到谈话
现在求奶牛两两交流成功需要的分贝*距离的总和。
【题解】
我们将奶牛对于需要的分贝排序，那么在计算的时候，
每头奶牛只要计算和序列前面所有奶牛的答案即可
那么只要维护前面所有奶牛和其距离之差的绝对值之和即可
将其拆分为坐标小于该奶牛的坐标之和，和大于该奶牛的部分
发现只要用线段树维护区间和以及区间数的个数即可。
【代码】
#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int N=20010;int T[N*4],C[N*4],n,t,c,M;struct data{int v,x;}p[N];long long ans;bool cmp(data a,data b){return a.v<b.v;}void add(int x,int y){ T[x+=M]+=y; C[x]++; for(x/=2;x;x/=2){ T[x]=T[x<<1]+T[(x<<1)^1]; C[x]=C[x<<1]+C[(x<<1)^1]; }}void query(int x,int y){ t=c=0; x+=M-1;y+=M+1; while(x^y^1>0){ if(~x&1)t+=T[x+1],c+=C[x+1]; if(y&1)t+=T[y-1],c+=C[y-1]; x>>=1;y>>=1; }}int main(){ for(M=1;M<N;M<<=1); while(~scanf("%d",&n)){ for(int i=1;i<=n;i++)scanf("%d%d",&p[i].v,&p[i].x); sort(p+1,p+n+1,cmp); memset(T,0,sizeof(T)); memset(C,0,sizeof(C)); for(int i=1;i<=n;i++){ query(1,p[i].x); ans+=1LL*p[i].v*(p[i].x*c-t); query(p[i].x,20000); ans+=1LL*p[i].v*(t-p[i].x*c); add(p[i].x,p[i].x); }printf("%lld\n",ans); }return 0;}POJ 1990 MooFest（zkw线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。