POJ1990：树状数组

POJ1990

题意&＃xff1a;

• 牛i和j沟通&＃xff0c;音量为abs(c[i].x-c[j].x) * max(c[i].v,c[j].v);
• 求任意两头牛通话的音量总和

题解

• 按牛的耳背程度从小到大排序
• 每加入一头牛&＃xff0c;其耳背程度一定是最大的。然后&＃xff0c;算出与之前牛的距离之和
• 维护距离≤xi的坐标之和sum&＃xff0c;和数量num&＃xff0c;则ans &＃43;&＃61; (num * c[i].x - sum) * c[i].v
• 同理可以算出距离&＃xff1e;xi的。

代码

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int const N &＃61; 20000 &＃43; 10;
ll n;
ll sum[N],num[N],ans;
struct Cow
{int v,x;bool operator <(const Cow& e) const{return v }c[N];
ll lowbit(ll x){return x&-x;}
void add(ll c[N],ll i,ll x){while(i <&＃61; N){c[i] &＃43;&＃61; x;i &＃43;&＃61; lowbit(i);}
}
ll getsum(ll c[N],ll i){ll sum &＃61; 0;while(i){sum &＃43;&＃61; c[i];i -&＃61; lowbit(i);}return sum;
}
int main(){scanf("%lld",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%lld%lld",&c[i].v,&c[i].x);sort(c&＃43;1,c&＃43;1&＃43;n);ll tot &＃61; 0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){int low &＃61; getsum(num,c[i].x-1); //比c[i].x小的数的个数ll s &＃61; getsum(sum,c[i].x-1); //比c[i].x小的距之和ans &＃43;&＃61; c[i].v * (low * c[i].x - s); ans &＃43;&＃61; c[i].v * ((tot - s) - c[i].x * (i - low - 1)); //比c[i].x大牛add(sum,c[i].x,c[i].x);add(num,c[i].x,1);tot &＃43;&＃61; c[i].x;}printf("%lld\n",ans);return 0;
}