kuangbin题单专题七线段树完结撒花%%%（终于写完了）

本题相当于亚特兰蒂斯进阶版，相当于对于每个面都来一遍扫描线

#include <bits/stdc++.h>

#pragma GCC optimize(3, "Ofast", "inline") // 吸氧真爽

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1010;

int T, n;
vector<int> ys, zs; // 离散化
int Case, idx;

struct node
{
    int l, r;
    int cnt, len1, len2, len3; // 维护覆盖一，二，三次的数
}tr[N * 8];

struct point // 存点
{
    int x1, y1, z1, x2, y2, z2;
}p[N * 8];

struct segment // 存每一条线段，和亚特兰蒂斯一样用前缀和的思想去维护面积
{
    int x, y1, y2, k;
    bool operator < (const segment & w) const
    {
        return x < w.x;
    }
}seg[N * 4];

int find(int x) // 对于离散化后的查找
{
    return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}

void push_up(node &root, node &l, node &r) // 分别更新覆盖一次，两次，三次
{
    if (root.cnt >= 1) root.len1 = ys[root.r + 1] - ys[root.l];
    else if (root.l != root.r) root.len1 = l.len1 + r.len1;
    else root.len1 = 0;

    if (root.cnt >= 2) root.len2 = ys[root.r + 1] - ys[root.l];
    else if (root.l == root.r) root.len2 = 0;
    else if (root.cnt == 1) root.len2 = l.len1 + r.len1;
    else root.len2 = l.len2 + r.len2;

    if (root.cnt >= 3) root.len3 = ys[root.r + 1] - ys[root.l];
    else if (root.l == root.r) root.len3 = 0;
    else if (root.cnt == 2) root.len3 = l.len1 + r.len1;
    else if (root.cnt == 1) root.len3 = l.len2 + r.len2;
    else root.len3 = l.len3 + r.len3;
}

void push_up(int u)
{
    push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) // 常规建树
{
    if (l == r) tr[u] = {l, r, 0, 0, 0, 0};
    else
    {
        tr[u] = {l, r, 0, 0, 0, 0};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
}

void modify(int u, int l, int r, int k) // 常规修改
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        push_up(u);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        push_up(u);
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> T;
    while (T --)
    {
        Case ++;
        cout << "Case " << Case << ':' << ' ';

        idx = 0;
        ys.clear(), zs.clear();

        cin >> n;
        for (int i = 0; i < n; i ++) // 因为z是在负五百开始，所以为了方便，可以把z都向上移500
        {
            int x1, y1, z1, x2, y2, z2;
            cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
            z1 += 500, z2 += 500;
            p[i] = {x1, y1, z1, x2, y2, z2};
            ys.push_back(y1), ys.push_back(y2);
            zs.push_back(z1), zs.push_back(z2);
        }

        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end()); // 离散，去重

        sort(zs.begin(), zs.end());
        zs.erase(unique(zs.begin(), zs.end()), zs.end()); // 离散，去重

        LL res = 0;
        int lastz = 0;

        for (int zz = 0; zz < zs.size(); zz ++)
        {
            build(1, 0, ys.size() - 2); // 对于每一个面都进行一次扫描线
            idx = 0;
            for (int i = 0; i < n; i ++)
            {
                if (p[i].z1 < zs[zz] && p[i].z2 >= zs[zz])
                {
                    int x1 = p[i].x1, x2 = p[i].x2, y1 = p[i].y1, y2 = p[i].y2;
                    seg[idx ++] = {x1, y1, y2, 1};
                    seg[idx ++] = {x2, y1, y2, -1};
                }
            }
            sort(seg, seg + idx);
            for (int i = 0; i < idx; i ++)
            {
                if (i != 0) res += (LL)1 * (seg[i].x - seg[i - 1].x) * tr[1].len3 * (zs[zz] - lastz);
                modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
            }
            lastz = zs[zz]; // 存下上一次的z的坐标，方便计算体积
        }

        cout << res << '\n';
    }

    return 0;
}