poj 3277...离散化+线段树...

(1)线段树数组开的太小会WA。

(2)强制类型转换的时机不对会溢出，这么幼稚的问题竟然疏忽了。

(3)插入新线段的时候修改就深入到线段元会TLE，不妨使用lazy的思想，线段树结点中的h域就是tag。

(4)离散化，脑海中竟然浮现的是Riemann-Stieltjes积分和Riemann积分的定义。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int MAXN = 40005;

typedef struct {
    int a;
    int b;
    int h;
}Building;

typedef struct {
    int l;
    int r;
    int h;
}Node;

int N;
Building p[MAXN];

int idx[MAXN << 1];
Node seg[MAXN << 3];

__int64 ans;

void build(int num,int l,int r)
{
    seg[num].l = l;
    seg[num].r = r;
    seg[num].h = 0;
    
    if ( l + 1 == r )
        return;
    int m = ( l + r ) >> 1;
    build(num << 1, l, m);
    build(num << 1 | 1, m, r);
}

void insert(int num,int l,int r,int h)
{
    if ( idx[seg[num].l] == l && idx[seg[num].r] == r )
    {
        seg[num].h = h;
        return;
    }

    int m = ( seg[num].l + seg[num].r ) >> 1;
    if ( r <= idx[m] )
        insert(num << 1, l, r, h);
    else if ( idx[m] <= l )
        insert(num << 1 | 1, l, r, h);
    else
    {
        insert(num << 1, l, idx[m], h);
        insert(num << 1 | 1, idx[m], r, h);
    }
}


void walk(int num,int h)
{
    if ( seg[num].h < h )
        seg[num].h = h;
    if ( seg[num].l + 1 == seg[num].r )
    {
        ans += (__int64)( idx[seg[num].r] - idx[seg[num].l] ) * seg[num].h;
        return;
    }
    walk(num << 1, seg[num].h);
    walk(num << 1 | 1, seg[num].h);
}

bool cmp(Building& x,Building& y)
{
    return x.h <= y.h;
}

int main()
{
//    freopen("2.txt","r",stdin);

    int i;
    scanf("%d",&N);
    for ( i = 1; i <= N; i++)
        scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].h);
    
    sort(p + 1, p + 1 + N, cmp);
    
    int cnt = 0;
    for ( i = 1; i <= N; i++)
    {
        idx[++cnt] = p[i].a;
        idx[++cnt] = p[i].b;
    }

    sort(idx + 1, idx + cnt + 1);

    int n = unique(idx + 1, idx + 1 + cnt) - ( idx + 1 );

    build(1,1,n);

    for ( i = 1; i <= N; i++)
        insert(1, p[i].a, p[i].b, p[i].h);

    walk(1, 0);

    printf("%I64d\n",ans);

    return 0;
}

poj 3277...离散化+线段树...

推荐阅读