Get The Treasury【HDU-3642】【扫描线】

题目给出的是N个体积块，问的是有多少体积重叠了3次及以上？

那么就是怎么处理体积这样子的问题了，看到Z的种类不多的时候，就想着从Z离散化的角度去考虑这个问题了，然后就是怎样子去处理面积了，这时候想到每一个Z所代表的这个面对应上的体积，然后把每个面都处理出来看，体积就是在处理X的和，以及求Y、Z的差（差分）来的乘积，所以在处理Z上的时候也有些细节的东西，就是我们要考虑到目前所访问到的这个面积段是否是可以取的，也就是要去判断它的上下Z坐标和目前的区间的上下Z坐标的关系式了。

另外，在处理pushup()的时候，也是需要注意细节，我在这里处理的是"≥times"也就是覆盖次数大于等于1的线段的长、大于等于2的线段的长……

剩下的吧，基本就是写代码上的，细心点，没什么其他的了。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

#include <limits>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#define lowbit(x) ( x&(-x) )

#define pi 3.141592653589793

#define e 2.718281828459045

#define INF 0x3f3f3f3f

#define HalF (l + r)>>1

#define lsn rt<<1

#define rsn rt<<1|1

#define Lson lsn, l, mid

#define Rson rsn, mid+1, r

#define QL Lson, ql, qr

#define QR Rson, ql, qr

#define myself rt, l, r

using namespace std;

typedef unsigned long long ull;

typedef long long ll;

const int maxN = 1e3 + ;

int N, X[maxN<<], tot, Z[maxN<<], cnt, lsan_Z, _UP;

struct IOput

{

    int lx, ly, lz, rx, ry, rz;

}a[maxN];

struct node

{

    int lx, rx, y, val;

    node(int a=, int b=, int c=, int d=):lx(a), rx(b), y(c), val(d) {}

}line[maxN<<];

bool cmp(node e1, node e2) { return e1.y < e2.y; }

struct Tree

{

    int siz, sum, len1, len2;   //求的是"≥times"的数的个数和

    void clear() { siz = sum = len1 = len2 = ; }

}t[maxN<<];

inline void buildTree(int rt, int l, int r)

{

    t[rt].clear();

    if(l == r) return;

    int mid = HalF;

    buildTree(Lson);

    buildTree(Rson);

}

inline void pushup(int rt, int l, int r)

{

    if(t[rt].siz >= )

    {

        t[rt].sum = t[rt].len2 = t[rt].len1 = X[r + ] - X[l];

    }

    else if(t[rt].siz == )

    {

        t[rt].sum = t[lsn].len1 + t[rsn].len1;

        t[rt].len2 = t[rt].len1 = X[r + ] - X[l];

    }

    else if(t[rt].siz == )

    {

        t[rt].sum = t[lsn].len2 + t[rsn].len2;

        if(l == r) t[rt].len2 = ;  //相等的时候记得清空对应值

        else t[rt].len2 = t[lsn].len1 + t[rsn].len1;

        t[rt].len1 = X[r + ] - X[l];

    }

    else if(l == r) t[rt].clear();

    else

    {

        t[rt].sum = t[lsn].sum + t[rsn].sum;

        t[rt].len2 = t[lsn].len2 + t[rsn].len2;

        t[rt].len1 = t[lsn].len1 + t[rsn].len1;

    }

}

inline void update(int rt, int l, int r, int ql, int qr, int val)

{

    if(ql <= l && qr >= r)

    {

        t[rt].siz += val;

        pushup(myself);

        return;

    }

    int mid = HalF;

    if(qr <= mid) update(QL, val);

    else if(ql > mid) update(QR, val);

    else { update(QL, val); update(QR, val); }

    pushup(myself);

}

inline void init()

{

    cnt = ;

}

int main()

{

    int T;  scanf("%d", &T);

    for(int Cas=; Cas<=T; Cas++)

    {

        scanf("%d", &N);

        init();

        for(int i=; i<=N; i++)

        {

            scanf("%d%d%d%d%d%d", &a[i].lx, &a[i].ly, &a[i].lz, &a[i].rx, &a[i].ry, &a[i].rz);

            Z[++cnt] = a[i].lz;

            Z[++cnt] = a[i].rz;

        }

        sort(Z + , Z + cnt + );

        lsan_Z = (int)(unique(Z + , Z + cnt + ) - Z - );

        ll ans = ;

        for(int u=; u<lsan_Z; u++)

        {

            tot = ;

            for(int i=; i<=N; i++)

            {

                if(a[i].lz <= Z[u] && a[i].rz > Z[u])   //不能计算前面已经算过的部分，就是存在头即尾的情况

                {

                    line[++tot] = node(a[i].lx, a[i].rx, a[i].ly, );

                    X[tot] = a[i].lx;

                    line[++tot] = node(a[i].lx, a[i].rx, a[i].ry, -);

                    X[tot] = a[i].rx;

                }

            }

            sort(line + , line + tot + , cmp);

            sort(X + , X + tot + );

            _UP = (int)(unique(X + , X + tot + ) - X - );

            memset(t, , sizeof(t));

            for(int i=, l, r; i<tot; i++)

            {

                l = (int)(lower_bound(X + , X + _UP + , line[i].lx) - X);

                r = (int)(lower_bound(X + , X + _UP + , line[i].rx) - X - );

                update(, , _UP, l, r, line[i].val);

                ans += (ll)(Z[u + ] - Z[u]) * (ll)(line[i + ].y - line[i].y) * (t[].sum);

            }

        }

        printf("Case %d: %lld\n", Cas, ans);

    }

    return ;

}

/*

1

6

1 0 0 2 2 2

0 1 0 2 2 2

0 0 1 2 2 2

1 0 0 2 2 2

0 1 0 2 2 2

0 0 1 2 2 2

ans = 4

*/

巴特西

Get The Treasury【HDU-3642】【扫描线】

最新文章

热门文章