HDU 3642 Get The Treasury(Segment Tree Scanning Lines)

Description

长方体相交，求相交至少3次部分的体积

Analyze

相交至少三次与相交至少两次的处理方法一样

然后三维，降维做题，遍历Z轴，一层一层地求解

还有一点要注意，ans += len3[1] * (e[i + 1].h - e[i].h);不行了，相邻的两个面，e[i + 1]与e[i]只是y轴上相邻，Z轴上可能天上地下，所以用一个变量last记录本层前一个y

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20010;

int n;

int num;
int X[N];
int cnt[N << 2 | 1];
int len1[N << 2 | 1], len2[N << 2 | 1], len3[N << 2 | 1];

struct edge
{
    int l, r, h, zd, zu;
    int flag;
    edge(int a, int b, int c, int d, int f, int g):l(a), r(b), h(c), flag(d), zd(f), zu(g) {}
    edge() {}
    bool operator < (const edge & t)const
    {
        return h < t.h;
    }
} e[N];

void up(int o, int L, int R)
{
    if(cnt[o])
        len1[o] = X[R + 1] - X[L];
    else if(L == R)
        len1[o] = 0;
    else
        len1[o] = len1[o << 1] + len1[o << 1 | 1];

    if(cnt[o] >= 2)
        len2[o] = X[R + 1] - X[L];
    else if(L == R)
        len2[o] = 0;
    else
    {
        if(cnt[o] == 1)
            len2[o] = len1[o << 1] + len1[o << 1 | 1];
        else
            len2[o] = len2[o << 1] + len2[o << 1 | 1];
    }

    if(cnt[o] >= 3)
        len3[o] = X[R + 1] - X[L];
    else if(L == R)
        len3[o] = 0;
    else
    {
        if(cnt[o] == 2)
            len3[o] = len1[o << 1] + len1[o << 1 | 1];
        else if(cnt[o] == 1)
            len3[o] = len2[o << 1] + len2[o << 1 | 1];
        else
            len3[o] = len3[o << 1] + len3[o << 1 | 1];
    }
}

void update(int o, int L, int R, int l, int r, int val)
{
    if(L > r || R < l)
        return ;
    if(l <= L && R <= r)
    {
        cnt[o] += val;
        up(o, L, R);
        return ;
    }
    if(L == R)
        return ;

    int mid = (L + R) >> 1;
    update(o << 1, L, mid, l, r, val);
    update(o << 1 | 1, mid + 1, R, l, r, val);
    up(o, L, R);
}

int main()
{
    int _, t = 1;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d", &n);
        num = 0;
        int a, b, c, d, f, g;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d %d %d %d %d %d", &a, &b, &f, &c, &d, &g);
            X[num] = a;
            e[num++] = edge(a, c, b, 1, f, g);
            X[num] = c;
            e[num++] = edge(a, c, d, -1, f, g);
        }

        sort(e, e + num);
        sort(X, X + num);
        int m = unique(X, X + num) - X;

        long long ans = 0;
        for(int z = -500; z <= 500; ++z)
        {
            memset(cnt, 0, sizeof(cnt));
            memset(len1, 0, sizeof(len1));
            memset(len2, 0, sizeof(len2));
            memset(len3, 0, sizeof(len3));
            int last = 0;
            for(int i = 0; i < num; ++i)
            {
                if(z >= e[i].zd && z < e[i].zu)
                {
                    int l = lower_bound(X, X + m, e[i].l) - X;///Segment Tree begins with 0
                    int r = lower_bound(X, X + m, e[i].r) - X - 1;
                    ans += (long long)len3[1] * (e[i].h - last);
                    update(1, 0, m - 2, l, r, e[i].flag);
                    last = e[i].h;
                }
            }
        }
        printf("Case %d: %lld\n", t++, ans);
    }
    return 0;
}