BZOJ-3225 立方体覆盖 线段树+扫描线+乱搞

时间：2021-05-12 08:13:47
看数据范围像是个暴力，而且理论复杂度似乎可行，然后被卡了两个点。。。然后来了个乱搞的线段树+扫描线。。

3225: [Sdoi2008]立方体覆盖

Time Limit: 2 Sec Memory Limit: 128 MB

Submit: 102 Solved: 64

[Submit][Status][Discuss]

Description

　　A君近日为准备省队选拔，特意进行了数据结构的专项训练。训练过程中就遇到了“矩形面积并”这道经典问题，即：给出N个各边与坐标轴平行(垂直)的矩形，求矩形覆盖的面积之和。A君按纵坐标建立线段树后按横坐标扫描计算，轻易AC了这道题，时间复杂度为O(NlogN)。

　　为了强化训练，A君将问题推广到三维空间中，即：给出N个各棱与坐标轴平行(垂直)的立方体，求立方体覆盖的体积之和。为了简化问题，令立方体均退化为正立方体，用四元组(x, y, z, r)表示一个立方体，其中x, y, z为立方体的中心点坐标，r为中心点到立方体各个面的距离(即立方体高的一半)。

　　这次可难住了A君，只好请你——未来的金牌——来帮助他了。

Input

　　第一行是一个正整数N。

　　以下N行每行四个整数x, y, z, r，由空格隔开。

Output

　　共一个数，即覆盖的总体积。

Sample Input

3

0 0 0 3

1 –1 0 1

19 3 5 6

Sample Output

1944

HINT

对于 100% 的数据，1≤N≤100

对于 100% 的数据，-1000≤x, y, z≤1000，1≤r≤200

线段树+扫描线怎么搞非常容易，即确定一个轴离散另一个，然后分段扫描求面积求和即可。此题二维，可以同理。

直接写个二维的线段树（线段树套线段树）会舒服很多，可惜树套树不是很会，于是乱搞了个。。

于是我先枚举离散后的高，再次基础上控制满足条件的x，y。

利用扫描线的思想，把每一条竖边取出并按x从左到右快排，然后扫描。如果一条边是始边，把线段树中的y1–y2加1，否则把y1–y2减1。然后对于每一个不同的x，把线段树中覆盖层数大于1的个数*(x[i+1]-x[i])。

这个线段树的细节很多，比如线段树建立是l~mid,mid~r，然后叶子节点是l~l+1。

code：

#include<cstdio>

#include<algorithm>

using namespace std;

int read()

{

    int x=0,f=1; char ch=getchar();

    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

#define maxn 1010

const int ff=1200;

struct tre{int sum,del,l,r;}tree[210*2*16];

int x1[110],x2[110],y1[110],y2[110],z1[110],z2[110];

int tz,tZ,ty,tY;;

int Z[220],Y[220],z[220],y[220];

int n,t,tmp;

int ans=0;

struct data{int x,l,r,f;}xd[220];

int pp[2500];int to;

int L,R,F;int h,W;

void build(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r;

    tree[now].sum=tree[now].del=0;

    if (l==r || l+1==r) return;

    int mid=(l+r)>>1;

    build(now<<1,l,mid);

    build(now<<1|1,mid,r);

}

void insert(int now)

{

    if (L<=tree[now].l && R>=tree[now].r)

        {

            if (!F) tree[now].del++,tree[now].sum=y[tree[now].r]-y[tree[now].l]; else

            if (!(--tree[now].del)) tree[now].sum=(tree[now].l+1>=tree[now].r)?0:tree[now<<1].sum+tree[now<<1|1].sum;

            return;

        }

    int mid=(tree[now].l+tree[now].r)>>1;

    if (L<mid) insert(now<<1);

    if (R>mid)  insert(now<<1|1);

    if (!tree[now].del) tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;

}

bool cmp(data a,data b)

{

    if (a.x!=b.x) return a.x<b.x;

    return !a.f&&b.f;

}

int main()

{

    n=read();

    for (int i=1; i<=n; i++)

        {

            int xx=read(),yy=read(),zz=read(),r=read();

            x1[i]=xx-r;x2[i]=xx+r;

            y1[i]=yy-r;y2[i]=yy+r;

            z1[i]=zz-r;z2[i]=zz+r;

        }

    for (int i=1; i<=n; i++)

        Z[++tZ]=z1[i],Z[++tZ]=z2[i];

    sort(Z+1,Z+tZ+1);Z[0]=Z[1]-1;

    for (int i=1; i<=tZ; i++) if (Z[i]!=Z[i-1]) z[++tz]=Z[i];

    for (int i=1; i<tz; i++)

        {

            h=z[i+1]-z[i];

            t=ty=tY=0;

            to=tmp=0;

            for (int j=1; j<=n; j++)

                if (z1[j]<=z[i] && z[i+1]<=z2[j])

                    {

                        xd[++t].x=x1[j],xd[t].l=y1[j],xd[t].r=y2[j],xd[t].f=0;

                        xd[++t].x=x2[j],xd[t].l=y1[j],xd[t].r=y2[j],xd[t].f=1;

                        Y[++tY]=y1[j],Y[++tY]=y2[j];

                    }

            sort(Y+1,Y+tY+1);Y[0]=Y[1]-1;

            for (int j=1; j<=tY; j++) if (Y[j]!=Y[j-1]) y[++ty]=Y[j],pp[Y[j]+ff]=++to;

            if (!ty) continue;

            sort(xd+1,xd+t+1,cmp); build(1,1,ty);

            for (int j=1; j<t; j++)

                {

                    W=xd[j+1].x-xd[j].x;

                    L=pp[xd[j].l+ff],R=pp[xd[j].r+ff],F=xd[j].f;

                    insert(1);

                    if (xd[j+1].x!=xd[j].x || j+1==t) tmp+=tree[1].sum*W;

                }

            ans+=h*tmp;

        }

    printf("%d\n",ans);

    return 0;

}

相关文章