hdu 3642 Get The Treasury (线段树+扫描线,求长方体体积交)

Posted by 111qqz on Friday, September 29, 2017

TOC

hdu3642题目链接

题意:给出若干个(1000)长方体,求至少交三次的空间的体积。

尺寸为[x1,x2],[y1,y2],[z1,z2],其中x,y的坐标的绝对值不超过1E6,Z的坐标的绝对值不超过1E9.

思路:

线段树+扫描线。

由于Z的坐标范围比较小,我们的做法是 利用“微分”的思想,将每个长方体,想成若干的高度为1的矩形(矩形片)

因此就转化成了求矩形至少交三次的面积

其中和矩形交,也就是矩形至少交2次的面积比较类似,只不过线段树多维护一个至少三次覆盖的长度的域。

void PushUp(int l,int r,int rt)
{
    //cout<<"l:"<<l<<" r:"<<r<<" rt:"<<rt<<" id:"<<id<<endl;
    if (tree[rt].cnt>=3)
    {
        tree[rt].one = tree[rt].two = tree[rt].three = X[r+1]-X[l];
    }
    else 
    if (tree[rt].cnt==2)
    {
    tree[rt].one = tree[rt].two = X[r+1]-X[l];
    
    if (l==r) tree[rt].three = 0 ;
    else tree[rt].three = tree[rt<<1].one + tree[rt<<1|1].one;

    }else if (tree[rt].cnt==1)
    {
        tree[rt].one = X[r+1] - X[l];

    if (l==r) tree[rt].two = tree[rt].three = 0;
    else 
    {
        tree[rt].two = tree[rt<<1].one + tree[rt<<1|1].one;
        tree[rt].three = tree[rt<<1].two + tree[rt<<1|1].two;
    }
    }
    else
    {
    if (l==r) tree[rt].one = tree[rt].two =  tree[rt].three = 0;
    else 
    {
        tree[rt].one = tree[rt<<1].one + tree[rt<<1|1].one;
        tree[rt].two = tree[rt<<1].two + tree[rt<<1|1].two;
        tree[rt].three = tree[rt<<1].three + tree[rt<<1|1].three;
    }
    }
}

假设我们有一个长为5,宽为6,高为7的长方体

那么我们就要将其拆成7个,长为5,宽为6的矩形

将所有长方体处理完之后,枚举高度,对于每一个高度,如果矩形大于等于三个,就做一个“矩形的三次面积交”操作,将答案累加。

2A,PushUp的时候写错了一句。。。即如果父亲节点已经覆盖了两次,那么父亲节点被覆盖三次的是从左右儿子被覆盖一次的情况得来的

/* ***********************************************
Author :111qqz
Created Time :2017年09月28日 星期四 14时18分35秒
File Name :hdu3642.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=2E3+7;
int n;
struct Seg
{
    LL l,r,h;
    int d;
    Seg(){}
    Seg(LL l,LL r,LL h,int d):l(l),r(r),h(h),d(d){}
    bool operator < (const Seg & rhs)const
    {
    return h < rhs.h;
    }
}a[N];
struct Tree
{
    LL one,two,three;
    int cnt;
}tree[N<<2];
LL X[N],Z[N];
struct Cube
{
    LL  x1,y1,z1,x2,y2,z2;
}cube[N];
struct Rec
{
    LL x1,y1,x2,y2;
    void print()
    {
    printf("x1:%lld y1:%lld x2:%lld y2:%lld\n",x1,y1,x2,y2);
    }
    Rec(){}
    Rec(LL x1, LL y1,LL x2, LL y2):x1(x1),y1(y1),x2(x2),y2(y2){}
};
vector< Rec >rec[N];
void PushUp(int l,int r,int rt)
{
    //cout<<"l:"<<l<<" r:"<<r<<" rt:"<<rt<<" id:"<<id<<endl;
    if (tree[rt].cnt>=3)
    {
        tree[rt].one = tree[rt].two = tree[rt].three = X[r+1]-X[l];
    }
    else 
    if (tree[rt].cnt==2)
    {
    tree[rt].one = tree[rt].two = X[r+1]-X[l];
    
    if (l==r) tree[rt].three = 0 ;
    else tree[rt].three = tree[rt<<1].one + tree[rt<<1|1].one;

    }else if (tree[rt].cnt==1)
    {
        tree[rt].one = X[r+1] - X[l];

    if (l==r) tree[rt].two = tree[rt].three = 0;
    else 
    {
        tree[rt].two = tree[rt<<1].one + tree[rt<<1|1].one;
        tree[rt].three = tree[rt<<1].two + tree[rt<<1|1].two;
    }
    }
    else
    {
    if (l==r) tree[rt].one = tree[rt].two =  tree[rt].three = 0;
    else 
    {
        tree[rt].one = tree[rt<<1].one + tree[rt<<1|1].one;
        tree[rt].two = tree[rt<<1].two + tree[rt<<1|1].two;
        tree[rt].three = tree[rt<<1].three + tree[rt<<1|1].three;
    }
    }
}
void update( int L,int R,int val,int l,int r,int rt)
{
    if (L<=l && r<=R)
    {
    tree[rt].cnt +=val;
    PushUp(l,r,rt);
    return;
    }
    int m = (l+r)>>1;
    if (L<=m) update(L,R,val,lson);
    if (R>=m+1) update(L,R,val,rson);
    PushUp(l,r,rt);
}

LL solve( int z)
{
    int siz = rec[z].size();
    if (siz<3) return 0LL;
   // for ( int i = 0 ; i < siz ; i++) rec[z][i].print();
    ms(tree,0);
    for ( int i = 0 ; i < siz ; i++)
    {
    LL x1 = rec[z][i].x1;
    LL y1 = rec[z][i].y1;
    LL x2 = rec[z][i].x2;
    LL y2 = rec[z][i].y2;
//  printf("x1:%lld y1:%lld x2:%lld y2:%lld\n",x1,y1,x2,y2);
    X[i+1] = x1;
    X[i+1+siz] = x2;
    a[i+1]=Seg(x1,x2,y1,1);
    a[i+1+siz]=Seg(x1,x2,y2,-1);
    }
    siz<<=1;
    sort(X+1,X+siz+1);
    sort(a+1,a+siz+1);
    int m = unique(X+1,X+siz+1)-X-1;
    LL ret = 0;
    for ( int i = 1 ; i < siz; i++)
    {
    int l = lower_bound(X+1,X+m+1,a[i].l)-X;
    int r = lower_bound(X+1,X+m+1,a[i].r)-X;
    update(l,r-1,a[i].d,1,m,1);
    ret += tree[1].three * (a[i+1].h-a[i].h);
    }
    //cout<<"Z:"<<z<<" ret:"<<ret<<endl;
    return ret;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
  #endif
    int T;
    int cas =  0;
    cin>>T;
    while (T--)
    {
        scanf("%d",&n);
        ms(tree,0);
        for ( int i = 0 ; i < N ; i++) rec[i].clear();
        for ( int i = 1 ; i <= n ; i++)
        {
        scanf("%lld %lld %lld",&cube[i].x1,&cube[i].y1,&cube[i].z1);
        scanf("%lld %lld %lld",&cube[i].x2,&cube[i].y2,&cube[i].z2);
        //此处先存储下来是为了将Z坐标离散化
        Z[i] = cube[i].z1;
        Z[i+n] = cube[i].z2;
        for ( int j = cube[i].z1 ; j < cube[i].z2 ; j++)
        {
                    rec[j+500].PB(Rec(cube[i].x1,cube[i].y1,cube[i].x2,cube[i].y2));
        }
        }
        LL ans = 0;
        for ( int i = 0 ; i <=1000 ; i++)
        {
        ans += solve(i);
        }
        printf("Case %d: %lld\n",++cas,ans);
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付