首页 > 代码库 > HDU 3015 Disharmony Trees（树状数组）
HDU 3015 Disharmony Trees（树状数组）
题意：给你n棵树，每棵树上有两个权值X H
对于X离散化 ：3 7 1 5 3 6 -> 2 6 1 4 2 5,对于H一样
然后F = abs(X1-X2) S=min(H1,H2)
求出每一对F*S的总和
可以看到一边是求每个数与其他数的最小值，一边是求每个数与其他数的差距。因此我们可以排序一边，处理另一边。
我们排序H，因为这样对于固定一个Xi Hi，从小到大每次都是Hi去乘以Xi与剩下的所有X的差的总和。
这样我们就可以使用树状数组维护两个值：每个位置值的个数，每个位置值的总大小，接着细心点处理就好了
#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<vector>#include<string>#include<cstdio>#include<cstring>#include<stdlib.h>#include<iostream>#include<algorithm>using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0#define mul(a,b) (a<<b)#define dir(a,b) (a>>b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=100010;struct node{ int sub,minx;} tree[Max];int n;bool cmpt(struct node p1,struct node p2){ return p1.sub<p2.sub;}bool cmp(struct node p1,struct node p2){ return p1.minx<p2.minx;//按照最值排序才能固定一个值}int lowbit(int x){ return x&(-x);}void Add(ll *bit,int x,ll y){ while(x<=n) { bit[x]+=y; x+=lowbit(x); } return;}ll Sum(ll *bit,int x){ ll sum=0ll; while(x) { sum+=bit[x]; x-=lowbit(x); } return sum;}ll bit[Max],bit2[Max];//存个数 存大小ll Solve(){ ll ans=0ll; memset(bit,0ll,sizeof(bit)); memset(bit2,0ll,sizeof(bit2)); for(int i=0;i<n;++i) { Add(bit2,tree[i].sub,(ll)tree[i].sub); Add(bit,tree[i].sub,1ll); } for(int i=0;i<n;++i) { Add(bit2,tree[i].sub,(ll)-tree[i].sub); Add(bit,tree[i].sub,-1ll); // printf("%d\n",tree[i].sub); ans+=(ll)tree[i].minx*( Sum(bit2,n)-Sum(bit2,tree[i].sub)-(ll)tree[i].sub*(Sum(bit,n)-Sum(bit,tree[i].sub))+ (ll)tree[i].sub*Sum(bit,tree[i].sub)-Sum(bit2,tree[i].sub));//关键 //printf("%I64d %I64d\n",ans,Sum(bit2,n)-Sum(bit,n)*tree[i].sub); } return ans;}int main(){ int tmp; while(~scanf("%d",&n)) { for(int i=0; i<n; ++i) scanf("%d %d",&tree[i].sub,&tree[i].minx); sort(tree,tree+n,cmpt);//离散化 tree[n].sub=tree[n].minx=-1; tmp=1; for(int i=0; i<n; ++i) { if(tree[i].sub!=tree[i+1].sub) { tree[i].sub=tmp; tmp=i+2; } else { tree[i].sub=tmp; } } sort(tree,tree+n,cmp); tmp=1; for(int i=0; i<n; ++i) { if(tree[i].minx!=tree[i+1].minx) { tree[i].minx=tmp; tmp=i+2; } else { tree[i].minx=tmp; } } // for(int i=0;i<n;++i) // printf("%d %d\n",tree[i].sub,tree[i].minx); printf("%I64d\n",Solve()); } return 0;}
HDU 3015 Disharmony Trees（树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。