hdu 3015 Disharmony Trees

点击打开hdu 3015

思路: 树状数组

分析:

1 题目给定n棵树的横坐标和高度，然后给定横坐标排序后的rank_f已及树的高度排序后的rank_s，规定两颗树的FAR为abs(rank_f[i] , rank_f[j]) , SHORT为min(rank_s[i] . rank[_sj])，那么i和j的组合的值为FAR*SHORT，求所有组合方式的总和

2 我们按照树的高度从大到小排序，然后我们分别求出每棵树的rank_f和rank_s ， 然后我们就可以利用poj 1990

的思路去做

代码:

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

typedef __int64 int64;
const int MAXN = 1e5+10;

struct Node{
    int x;
    int h;
    int f;
    int s;
    bool operator<(const Node& s)const{
        if(h > s.h) 
            return true;
        else if(h == s.h && x > s.x)
            return true;
        return false;
    }
};
Node node[MAXN];
int n , num[MAXN];
int64 treeNum[MAXN];
int64 treeRank[MAXN];

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

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

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

void init(){
    int s = 1;
    sort(num+1 , num+n+1);
    for(int i = n ; i > 0 ; i--){
        if(i < n && node[i].h == node[i+1].h) 
            node[i].s = node[i+1].s;
        else
            node[i].s = s;
        s++;
        node[i].f = lower_bound(num+1 , num+n+1 , node[i].x)-num;
    }
}

int64 solve(){
    int64 ans = 0;
    sort(node+1 , node+n+1);
    init();
    memset(treeNum , 0 , sizeof(treeNum)); 
    memset(treeRank , 0 , sizeof(treeRank)); 

    int64 total = 0;
    for(int i = 1 ; i <= n ; i++){
        int64 f = node[i].f;
        int64 s = node[i].s;
        int64 count = getSum(f , treeNum);
        int64 sum = getSum(f , treeRank);
        
        ans += s*(count*f-sum);
        ans += s*(total-sum-(i-1-count)*f);

        add(f , 1 , treeNum);
        add(f , f , treeRank);
        total += f;
    }
    return ans;
}

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