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 ;

}