首页 > 代码库 > poj1990 树状数组
poj1990 树状数组
1990
题意:
每头牛有两个属性v,x,计算sigma(max(v[i],v[j])*abs(x[i]-x[j]))1<=i<j<=n
分析:对于max函数我们可以按v的值从小到大排序则ans = sigma(v[j]*abs(x[i]-x[j]))1<=i<j<=n且v[i]<=v[j]
那么如何处理abs函数呢?分开来讨论
ans = sigma(v[j]*(x[i]-x[j])) x[i]>=x[j]
+ sigma(v[j]*(x[j]-x[i])) x[i]<x[j]
如何快速的求得sigma的值呢?树状数组!!
这样我们就得到了算法:
先按v值从小到大排序,利用树状数组维护两个数组dist,cnt 其中dist[i] 维护的数坐标(x轴)小于等于i的距离前缀和,cnt[i]表示坐标i在当前时有没有牛(1有,0无),
维护的是当前排完序后坐标在[1,i]的牛的个数
那么排完序后枚举当前的牛i 统计在这之前坐标比牛i小的有多少l个,比它大的有多少r个,然后计算牛i到其他牛的权值(以保证牛i是当前以计算牛中v值最大)
权值= v[i]*( (l*x[i]-dist.sum(x[i]))左边的权值和 +(dist.sum(maxn)-dist.sum(x[i])-r*x[i]) 右边的权值和 )
其中dist.sum(x[i])表示当前坐标在牛i左边的所有坐标之和,那么l*x[i]就是sigma(x[i]-x[j]) x[i]>=x[j]
其中dist.sum(maxn)-dist.sum(x[i]) 就是坐标在[x[i],maxn]之间的所有牛的坐标之和 则其-r*x[i] 就是sigma(x[j]-x[i] ) x[i]<x[j]
每次算完权值后将当前的牛的信息加入树状数组里面
cnt.add(x[i],1);
dist.add(x[i],x[i]);
单点更新 cnt[x[i]]=1,dist[x[i]]=x[i]
附上代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<cmath> 9 #include<vector>10 #define maxn 10001011 #define maxm 10001012 #define mod 100000000000000000013 #define INF 0x3f3f3f3f14 using namespace std;15 typedef long long ll;16 inline int lowbit(int x){17 return x&-x;18 }19 struct BIT{20 int n;21 ll bit[maxn+10];22 void init(int N){23 n=N;24 for(int i=0;i<=n;++i)bit[i]=0;25 }26 void add(int x,int v){27 for(int i=x;i<=n;i+=lowbit(i))bit[i]+=v;28 }29 ll sum(int x){30 ll ans=0;31 for(int i=x;i>0;i-=lowbit(i))ans+=bit[i];32 return ans;33 }34 }dist,cnt;35 pair<int,int>cow[maxn];36 int main (){37 int n;38 while(scanf("%d",&n)!=EOF){39 dist.init(maxn);40 cnt.init(maxn);41 for(int i=1;i<=n;++i){42 scanf("%d%d",&cow[i].first,&cow[i].second);43 }44 sort(cow+1,cow+n+1);45 ll ans=0;46 for(int i=1;i<=n;++i){47 int v = cow[i].first;48 int x = cow[i].second;49 ll l = cnt.sum(x);//左边已有有多少个50 ll r = cnt.sum(maxn)-cnt.sum(x);//右边已有多少个51 ans+=v*(l*x-dist.sum(x));//左边权值和52 ans+=v*(dist.sum(maxn)-dist.sum(x)-r*x);//右边权值和53 cnt.add(x,1);54 dist.add(x,x);55 }56 printf("%lld\n",ans);57 }58 }