POJ-1990 MooFest---两个树状数组

题目链接：

https://vjudge.net/problem/POJ-1990

题目大意：

一群牛参加完牛的节日后都有了不同程度的耳聋，第i头牛听见别人的讲话，别人的音量必须大于v[i]，当两头牛i，j交流的时候，交流的最小声音为max{v[i],v[j]}*他们之间的距离。现在有n头牛，求他们之间两两交流最少要的音量和。

解题思路：

使用树状数组，首先将二元组按照v的大小从小到大排序，这样可以保证每头牛比前面的牛的v大，计算它和它前面牛的音量和的时候，就可以直接用该头牛的v，还需要计算出|a[i].x - x|绝对值之和。

用树状数组维护坐标x，可以直接求出比这头牛小的所有x之和，还需要用另一个树状数组维护每个元素出现的次数，直接求出小于这头牛的x的牛的数目。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<map>

 #include<set>

 #include<cmath>

 #include<algorithm>

 #include<vector>

 #include<sstream>

 #define lowbot(i) (i&(-i))

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5 + ;

 struct cow

 {

     ll v, x;

     bool operator <(const cow& a)const

     {

         return v < a.v || v == a.v && x < a.x;

     }

 }a[maxn];

 int tree[maxn], id_num[maxn];

 void add(int x, int d, int tree[])

 {

     while(x <= maxn)//上限是maxn

     {

         tree[x] += d;

         x += lowbot(x);

     }

 }

 ll sum(int x, int tree[])

 {

     ll ans = ;

     while(x)

     {

         ans += tree[x];

         x -= lowbot(x);

     }

     return ans;

 }

 int main()

 {

     int n;

     scanf("%d", &n);

     for(int i = ; i < n; i++)scanf("%lld%lld", &a[i].v, &a[i].x);

     sort(a, a + n);

     ll num, tot, ans = ;

     for(ll i = ; i < n; i++)

     {

         num = sum(a[i].x, id_num);

         tot = sum(a[i].x, tree);

         ans += (num * a[i].x - tot) * a[i].v;

         //cout<<num<<" - "<<tot<<" + "<<ans<<endl;

         num = i - num;

         tot = sum(, tree) - tot;

         ans += (tot - num * a[i].x) * a[i].v;

         //cout<<num<<" - "<<tot<<" - "<<ans<<endl;

         add(a[i].x, a[i].x, tree);

         add(a[i].x, , id_num);

     }

     cout<<ans<<endl;

     return ;

 }