poj 1990 MooFest

思路: 樹狀數組

分析:

1 題目給定n頭牛的聽力v[i]. 現在規定兩頭你i和j如果要進行交流的話那麼消耗的能量就是dis(i,j)*max(v[i].v[j])，現在問n頭牛總共的n*(n-1)*2種方式消耗的總的能量

2 題目要求的是所有的牛的交流方式的總的消耗能量

   看這個樣例

   3 1

   2 5

   2 6

   4 3

   那麼所有的區間為[1.3],[1,5],[1,6],[3,5],[3,6],[5,6]

   那麼總和為4*dis[1.3]+3*dis[1,5]+3*dis[1,6]+4*dis[3,5]+4*dis[3,6]+2*dis[5,6] = 4*(dis[1.3]+dis[3,5]+dis[3,6])+3*(dis[1,5]+dis[1,6])+2*(dis[5,6]);

   那麼題目要求的ans = ∑(v[i]*(所有比v[i]小的牛的坐標的總和))

3 那麼我們來分解這個式子，我們對點按照音量的值從小到大排完序之後

   那麼對於任一的一點i，i之前的牛的音量值肯定小於v[i]，但是坐標的值可能比x[i]大也可能比x[i]小，因此我們應該分成兩部分來考慮，就是坐標是i的左邊和右邊

   首先考慮左邊的情況，假設左邊比小於等於v[i]的牛有三頭坐標分別為a b c，那麼左邊的值就是v[i]*(x[i]-a)+v[i]*(x[i]-b)+v[i]*(x[i]-c) => v[i]*(3*x[i]-(a+b+c))

   那麼我們假設左邊小於v[i]的牛有countLeft頭，總的坐標為totalLeft，那麼左邊的值為v[i]*(countLeft*x[i]-totalLeft);

   接下來考慮右邊的情況，由於我們已經按照v的值排序，那麼我們能夠很好的計算出小於等於v[i]的音量值的總的坐標之後，我們設為totalDis，那麼根據左邊求出的小於

   等於v[i]的個數為countLeft，那麼右邊的個數為i-countLeft，那麼同理右邊的坐標之和為totalDis-totalLeft , 那麼右邊的值為v[i]*(totalDis-totalLeft-(i-countLeft)*x[i]);

   那麼對於排序後的第i頭牛來說比它小的音量的牛的值為v[i]*(countLeft*x[i]-totalLeft)+v[i]*(totalDis-totalLeft-(i-countLeft)*x[i]);

4 我們已經知道了公式，現在我們只要去求countLeft和totalLeft即可，由於我們已經按照v的值排序， 那麼我們只要對坐標建立兩個樹狀數組即可。一個用來存儲個數，一個用來存儲坐標之和，那麼對於第i頭牛來說我們就能夠在O(logn)的時間內求出countLeft和totalLeft

代碼:

/***********************************************
* By: chenguolin                               * 
* Date: 2013-08-19                             *
* Address: http://blog.csdn.net/chenguolinblog *
***********************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MAXN = 20010;

struct Node{
    int x;
    int v;
    bool operator<(const Node& s)const{
        return v < s.v; 
    }
};
Node node[MAXN];
int n;
int treeCount[MAXN];
int treeDis[MAXN];

int lowbit(int x){
    return x&(-x);
}

int64 getSum(int x , int *arr){
    int64 sum = 0;
    while(x){
         sum += arr[x];
         x -= lowbit(x);
    }
    return sum;
}

void add(int x , int val , int *arr){
    while(x < MAXN){
         arr[x] += val; 
         x += lowbit(x); 
    }
}

int64 solve(){
    int64 ans = 0;
    int64 totalDis = 0;
    memset(treeCount , 0 , sizeof(treeCount));
    memset(treeDis , 0 , sizeof(treeDis));
    sort(node , node+n);

    for(int i = 0 ; i < n ; i++){
        int64 count = getSum(node[i].x , treeCount); 
        int64 dis = getSum(node[i].x , treeDis);
        // left
        ans += node[i].v*(count*node[i].x-dis);
        // right
        ans += node[i].v*((totalDis-dis-(i-count)*node[i].x));
        // update 
        totalDis += node[i].x;
        add(node[i].x , 1 , treeCount);
        add(node[i].x , node[i].x , treeDis);
    }
    return ans;
}

int main(){
    while(scanf("%d" , &n) != EOF){
         for(int i = 0 ; i < n ; i++) 
             scanf("%d%d" , &node[i].v , &node[i].x);
         printf("%lld\n" , solve());
    }
    return 0;
}