HDU 3642 Get The Treasury (线段树、扫描线求立方体体积交)

给定n个立方体，求这些立方体覆盖两次以上的体积。

之前做过求矩形面积交的题，这题可以转化为求矩形面积交。先对y坐标和z坐标离散化，然后枚举每个z轴区间，求在该区间内矩形覆盖两次以上的面积，再乘以该区间宽度，即为该区间覆盖两次以上的体积。由于更新节点时有些地方没考虑好，TLE和WA了几次。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <map>

using namespace std;

const int maxn = 2010;
int yy[maxn], zz[maxn];
int cov[maxn<<2], once[maxn<<2];
int twice[maxn<<2], more[maxn<<2];
map<int, int> my;
int t, n;

struct Point
{
    int x, y, z;
    void get()
    {
        scanf("%d%d%d", &x, &y, &z);
    }
};

struct Cube
{
    Point a, b;
}cube[maxn];

struct Line
{
    int y1, y2, x;
    int flag;
}line[maxn];

bool cmp(Line a, Line b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.flag > b.flag;
}

void addLine(int y1, int y2, int x, int flag, int idx)
{
    line[idx].y1 = y1;
    line[idx].y2 = y2;
    line[idx].x = x;
    line[idx].flag = flag;
}

void build(int l, int r, int rt)
{
    cov[rt] = once[rt] = twice[rt] = more[rt] = 0;
    if (l + 1 == r) return ;
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m, r, rt << 1 | 1);
}

void pushUp(int l, int r, int rt)
{
    if (cov[rt] > 2)
    {
        more[rt] = yy[r] - yy[l];
        once[rt] = twice[rt] = 0;
        return ;
    }
    if (cov[rt] == 2)
    {
        if (l + 1 == r)
        {
            twice[rt] = yy[r] - yy[l];
            once[rt] = more[rt] = 0;
        }
        else
        {
            more[rt] = more[rt<<1] + more[rt<<1|1] + twice[rt<<1] + 
                       twice[rt<<1|1] + once[rt<<1] + once[rt<<1|1];
            twice[rt] = yy[r] - yy[l] - more[rt];
            once[rt] = 0;
        }
        return ;
    }
    if (cov[rt] == 1)
    {
        if (l + 1 == r)
        {
            once[rt] = yy[r] - yy[l];
            twice[rt] = more[rt] = 0;
        }
        else
        {
            more[rt] = more[rt<<1] + more[rt<<1|1] + twice[rt<<1] + twice[rt<<1|1];
            twice[rt] = once[rt<<1] + once[rt<<1|1];
            once[rt] = yy[r] - yy[l] - twice[rt] - more[rt];
        }
        return ;
    }
    if (cov[rt] == 0)
    {
        if (l + 1 == r)
            more[rt] = twice[rt] = once[rt] = 0;
        else
        {
            more[rt] = more[rt<<1] + more[rt<<1|1];
            twice[rt] = twice[rt<<1] + twice[rt<<1|1];
            once[rt] = once[rt<<1] + once[rt<<1|1];
        }
        return ;
    }
}

void update(int L, int R, int c, int l, int r, int rt)
{
    if (L <= l && R >= r)
    {
        cov[rt] += c;
        pushUp(l, r, rt);
        return ;
    }
    if (l + 1 == r) return ;
    int m = (l + r) >> 1;
    if (L < m) update(L, R, c, l, m, rt << 1);
    if (R > m) update(L, R, c, m, r, rt << 1 | 1);
    pushUp(l, r, rt);
}

void solve()
{
    sort(yy, yy + n * 2);
    sort(zz, zz + n * 2);
    int cnty = 1;
    for (int i = 1; i < n * 2; ++i)
    {
        if (yy[i] != yy[cnty-1])
            yy[cnty++] = yy[i];
    }
    int cntz = 1;
    for (int i = 1; i < n * 2; ++i)
    {
        if (zz[i] != zz[cntz-1])
            zz[cntz++] = zz[i];
    }
    for (int i = 0; i < cnty; ++i)
        my[yy[i]] = i;
        
    long long ans = 0;
    build(0, cnty - 1, 1);
    for (int i = 0; i < cntz - 1; ++i)
    {
        int cnt = 0;
        for (int j = 0; j < n; ++j)
        {
            if (cube[j].a.z <= zz[i] && cube[j].b.z > zz[i])
            {
                addLine(cube[j].a.y, cube[j].b.y, cube[j].a.x, 1, cnt++);
                addLine(cube[j].a.y, cube[j].b.y, cube[j].b.x, -1, cnt++);
            }
        }
        sort(line, line + cnt, cmp);
        for (int j = 0; j < cnt - 1; ++j)
        {
            update(my[line[j].y1], my[line[j].y2], line[j].flag, 0, cnty - 1, 1);
            ans += (zz[i+1] - zz[i]) * (long long)more[1] * (line[j+1].x - line[j].x);
        }
        update(my[line[cnt-1].y1], my[line[cnt-1].y2], line[cnt-1].flag, 0, cnty - 1, 1);
    }
    printf("%I64d\n", ans);
}

int main()
{
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
        {
            cube[i].a.get();
            yy[i*2] = cube[i].a.y;
            zz[i*2] = cube[i].a.z;
            cube[i].b.get();
            yy[i*2+1] = cube[i].b.y;
            zz[i*2+1] = cube[i].b.z;
        }
        printf("Case %d: ", cas);
        solve();
    }
    return 0;
}