HDU 3642 Get The Treasury ( 线段树 求长方体体积并 )

求覆盖三次及其以上的长方体体积并。

这题跟 http://wenku.baidu.com/view/d6f309eb81c758f5f61f6722.html 这里讲的长方体体积并并不一样。

因为本题Z坐标范围非常小，所以可以离散化Z坐标，枚举每个体积块。

对每一个体积块：用底面积＊高求其体积。底面积直接用“线段树求长方形面积并”来得到即可。

对于覆盖次数，pushUp的时候：

1.满足 当前覆盖次数大于等于3的，直接求线段长。

2.小于3的，由 左右儿子覆盖次数＝3 - 当前覆盖次数 的两个儿子更新上来得到。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using namespace std;

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1 | 1

#define lc rt << 1

#define rc rt << 1 | 1

#define LL long long int

const int MAXN = ;

struct cube

{

    int x1, y1, z1;

    int x2, y2, z2;

    void readCube()

    {

        scanf( "%d%d%d", &x1, &y1, &z1 );

        scanf( "%d%d%d", &x2, &y2, &z2 );

        return;

    }

}cb[MAXN];

struct Line

{

    int s;  //sao ru sao chu

    int x;

    int y1, y2;

    Line() {}

    Line( int s, int x, int y1, int y2 ): s(s), x(x), y1(y1), y2(y2) { }

    void showLine()

    {

        printf("s=%d x=%d y1=%d y2=%d\n", s, x, y1, y2 );

        return;

    }

};

struct node

{

    int cnt;

    int len[];

};

int N;

node Tr[ MAXN <<  ];

Line L[ MAXN <<  ];

int Z[MAXN << ];

int Y[MAXN << ]; //li san hua

int cntZ, cntY;

bool cmp( const Line& a, const Line &b )

{

    if ( a.x != b.x ) return a.x < b.x;

    return a.s > b.s;

}

void build( int l, int r, int rt )

{

    for ( int i = ; i < ; ++i )

        Tr[rt].len[i] = ;

    Tr[rt].cnt = ;

    if ( l == r ) return;

    int m = ( l + r ) >> ;

    build( lson );

    build( rson );

    return;

}

void PushUp( int rt, int l, int r )

{

    //len0

    if ( Tr[rt].cnt >  )

        Tr[rt].len[] = Y[r+] - Y[l];

    else

        Tr[rt].len[] = Tr[lc].len[] + Tr[rc].len[];

    //len1

    if ( Tr[rt].cnt >  )

        Tr[rt].len[] = Y[r+] - Y[l];

    else if ( Tr[rt].cnt ==  )

        Tr[rt].len[] = Tr[lc].len[] + Tr[rc].len[];

    else

        Tr[rt].len[] = Tr[lc].len[] + Tr[rc].len[];

    //len2

    if ( Tr[rt].cnt >  )

        Tr[rt].len[] = Y[r+] - Y[l];

    else if ( Tr[rt].cnt ==  )

        Tr[rt].len[] = Tr[lc].len[] + Tr[rc].len[];

    else if ( Tr[rt].cnt ==  )

        Tr[rt].len[] = Tr[lc].len[] + Tr[rc].len[];

    else

        Tr[rt].len[] = Tr[lc].len[] + Tr[rc].len[];

    return;

}

void Update( int L, int R, int v, int l, int r, int rt )

{

    if ( L <= l && r <= R )

    {

        Tr[rt].cnt += v;

        PushUp( rt, l, r );

        return;

    }

    if ( l == r ) return;

    int m = ( l + r ) >> ;

    if ( L <= m ) Update( L, R, v, lson );

    if ( R > m )  Update( L, R, v, rson );

    PushUp( rt, l, r );

    return;

}

int main()

{

    int T, cas = ;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%d", &N );

        cntZ = ;

        cntY = ;

        for ( int i = ; i < N; ++i )

        {

            cb[i].readCube();

            Z[cntZ++] = cb[i].z1;

            Z[cntZ++] = cb[i].z2;

            Y[cntY++] = cb[i].y1;

            Y[cntY++] = cb[i].y2;

        }

        sort( Z, Z + cntZ );

        sort( Y, Y + cntY );

        cntZ = unique( Z, Z + cntZ ) - Z;

        cntY = unique( Y, Y + cntY ) - Y;

        LL ans = ;

        for ( int i = ; i < cntZ - ; ++i )

        {

            int cntL = ;

            for ( int j = ; j < N; ++j )

            {

                if ( cb[j].z1 <= Z[i] && cb[j].z2 >= Z[i + ] )

                {

                    L[cntL++] = Line( , cb[j].x1, cb[j].y1, cb[j].y2 );

                    L[cntL++] = Line(-, cb[j].x2, cb[j].y1, cb[j].y2 );

                }

            }

            sort( L, L + cntL, cmp );

            build( , cntY - ,  );

            for ( int k = ; k < cntL; ++k )

            {

                if ( k )

                    ans += (LL)( L[k].x-L[k-].x )*Tr[].len[]*( Z[i+]-Z[i] );

                int a = lower_bound( Y, Y + cntY, L[k].y1 ) - Y;

                int b = lower_bound( Y, Y + cntY, L[k].y2 ) - Y - ;   //这里一定要减1！！！！！！

                Update( a, b, L[k].s, , cntY - ,  );

            }

        }

        printf( "Case %d: %lld\n", ++cas, ans );

    }

    return ;

}

之前一直调试不出结果，是因为点树和线段树没分清楚，就是线段树节点中存的是一个点，还是一个单位长度倍数的线段。

对于二分得到a，b值，b值需要－1，而pushUp的时候r值需要＋1这里并不是很理解。