Get The Treasury HDU – 3642（体积扫描线）

给出n个立方体，要你求这些立方体至少被覆盖三次的部分。

先把这个立方体的信息存在来，发现Z的范围不大，z范围是是[-500,500]，所以我们可以先离散化，然后枚举Z，

然后对于每一段Z的区域内，在当前的区域内对xoy轴使用一次扫描线，找到当前这个区域内被覆盖三次的体积，然后每次枚举Z，每次相加，就是最后的答案。

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define first fi
#define second se
#define lowbit(x) (x & (-x))typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
using namespace std;int n, m, tol, T;
struct Node {
    int l, r, h, f;
    bool operator < (Node a) const {
        return h < a.h;
    }
};
Node node[maxn];
struct Edge {
    int x1, y1, z1;
    int x2, y2, z2;
};
Edge edge[maxn];
int Z[maxn];
int a[maxn];
int cnt[maxn << ];
int sum1[maxn << ];
int sum2[maxn << ];
int sum3[maxn << ];void init() {
    m = ;
    memset(cnt, , sizeof cnt);
    memset(sum1, , sizeof sum1);
    memset(sum2, , sizeof sum2);
    memset(sum3, , sizeof sum3);
    memset(node, , sizeof node);
}void pushup(int left, int right, int root) {
    if(cnt[root] >= ) {
        sum3[root] = sum2[root] = sum1[root] = a[right+] - a[left];
    } else if(cnt[root] == ) {
        sum2[root] = sum1[root] = a[right+] - a[left];
        sum3[root] = sum1[root << ] + sum1[root <<  | ];
    } else if(cnt[root] == ) {
        sum1[root] = a[right+] - a[left];
        sum3[root] = sum2[root << ] + sum2[root <<  | ];
        sum2[root] = sum1[root << ] + sum1[root <<  | ];
    } else {
        sum3[root] = sum3[root << ] + sum3[root <<  | ];
        sum2[root] = sum2[root << ] + sum2[root <<  | ];
        sum1[root] = sum1[root << ] + sum1[root <<  | ];
    }
}void update(int left, int right, int prel, int prer, int val, int root) {
    if(prel <= left && right <= prer) {
        cnt[root] += val;
        pushup(left, right, root);
        return ;
    }
    int mid = (left + right) >> ;
    if(prel <= mid)    update(left, mid, prel, prer, val, root << );
    if(prer > mid)    update(mid+, right, prel, prer, val, root <<  | );
    pushup(left, right, root);
}int main() {
    int T;
    scanf("%d", &T);
    int cas = ;
    while(T--) {
        memset(edge, , sizeof edge);
        memset(Z, , sizeof Z);
        scanf("%d", &n);
        for(int i=; i<=n; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            edge[i].x1 = x;
            edge[i].y1 = y;
            edge[i].z1 = z;
            Z[*i-] = z;
            scanf("%d%d%d", &x, &y, &z);
            edge[i].x2 = x;
            edge[i].y2 = y;
            edge[i].z2 = z;
            Z[*i] = z;
        }
        sort(Z+, Z++*n);
        int zz = unique(Z+, Z++*n) - (Z+);
        ll ans = ;
        for(int i=; i<zz; i++) {
            init();
            for(int j=; j<=n; j++) {
                if(edge[j].z1 <= Z[i] && Z[i+] <= edge[j].z2) {
                    node[m].l = edge[j].x1;
                    node[m].r = edge[j].x2;
                    node[m].h = edge[j].y1;
                    node[m].f = ;
                    a[m++] = edge[j].x1;
                    node[m].l = edge[j].x1;
                    node[m].r = edge[j].x2;
                    node[m].h = edge[j].y2;
                    node[m].f = -;
                    a[m++] = edge[j].x2;
                }
            }
            m--;
            sort(node+, node++m);
            sort(a+, a++m);
            int nn = unique(a+, a++m) - (a+);
            for(int j=; j<m; j++) {
                int l = lower_bound(a+, a++nn, node[j].l) - a;
                int r = lower_bound(a+, a++nn, node[j].r) - a;
                update(, m, l, r-, node[j].f, );
                ans += 1ll * sum3[] * (node[j+].h - node[j].h) * (Z[i+] - Z[i]);
            }
        }
        printf("Case %d: %lld\n", cas++, ans);
    }
    return ;
}