POJ PKU 3277 City Horizon 解题报告

#include<iostream>
#include<algorithm>
using  namespace std;
#define MAXN 40005
long index[MAXN * 3],num = 0;
struct Node
{
    long l,r,h;
};
bool cmp(Node a, Node b)
{
    return a.h < b.h;
}
Node old[MAXN],newN[MAXN * 10];//其中二叉树(newN)从1开始计数
void buildTree(long s,long e,long pos);
void addHeight(long s,long e,long h,long pos);
long binarySearch(long value,long s[] , long max);
__int64 getValue(Node s[] , long pos);
int main()
{
    long n,i;
    scanf("%ld",&n);
    for(i = 0 ; i < n ; i ++)
    {
        scanf("%ld %ld %ld",&old[i].l,&old[i].r,&old[i].h);
        index[num ++] = old[i].l;
        index[num ++] = old[i].r;
    }
    sort(index , index + num);
    num = 1;//合并区间
    for(i = 1 ; i < 2 * n ; i ++)
        if(index[i] != index[i - 1])
            index[num ++] = index[i];

    //按索引的下标建树
    buildTree(0,num - 1,1);

    sort(old , old + n , cmp);//按高度排序,方便覆盖低的高度
    for(i = 0 ; i < n ; i ++)
        addHeight(binarySearch(old[i].l , index , num) , binarySearch(old[i].r , index , num) , old[i].h , 1);

    cout<<getValue(newN ,1)<<endl;

    return 0;
}

void buildTree(long s,long e,long pos)
{
    newN[pos].l = s;
    newN[pos].r = e;
    newN[pos].h = 0;
    if(e > s + 1)
    {
        buildTree(s , (s + e) >> 1 , 2 * pos);
        buildTree((s + e) >> 1 , e , 2 * pos + 1);
    }
}
void addHeight(long s,long e,long h,long pos)
{
    if(newN[pos].l == s && newN[pos].r == e)
        newN[pos].h = h;//由于之前的排序这里只会被更大的值替换
    else
    {
        if(newN[pos].h)
            newN[2 * pos].h = newN[2 * pos + 1].h = newN[pos].h , newN[pos].h = 0;//同上
        long mid = (newN[pos].l + newN[pos].r) >> 1;
        if(e <= mid)
            addHeight(s , e , h , 2 * pos);
        else if(s >= mid)
            addHeight(s , e , h , 2 * pos + 1);
        else
        {
            addHeight(s , mid , h , 2 * pos);
            addHeight(mid , e , h , 2 * pos + 1);
        }
    }
}
long binarySearch(long value,long s[] , long max)
{
    long low = 0, high = max - 1;
    long mid;
    while(low <= high)
    {
        mid = (low + high) >> 1;
        if(value == s[mid])
            return mid;
        if(value > s[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    return 0;
}
__int64 getValue(Node s[] , long pos)
{
    if(s[pos].h)
        return (__int64)(index[s[pos].r] - index[s[pos].l]) * s[pos].h;
    if(s[pos].r - s[pos].l > 1)//等于1则是最后一个节点,无字节点,诺写>=1可能溢出
        return getValue(s, 2 * pos) + getValue(s , 2 * pos + 1);
    return 0;
}