HU-642-Get The Treasury(走査線＋線分樹、三次元)

3659 ワード
線分樹
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3642
三次元座標系を与え、n立方体を与え、三立方体でカバーされる体積とを求める.
考え方:z軸を離散的にして、平面でxy平面をスキャンします.各3 D印刷に似ています.スキャンの間隔に注意して、［z,z＋1］の範囲にない立方体はスキャンシーケンスを削除します.
ACCode:
#include
#include
#include
#include
#include
// srand(unsigned)time(NULL));rand();
  
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
  
#define ll long long
#define Pii pair
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
  
const int MAXN=4e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)

struct SegTree{
    struct Node{
        ll l,r;
        ll vl,vr;
        ll len1,len2,len3;
        ll flag;
    };
    Node Tree[MAXN<<2];
    
    void PushUp(int rt){
        if(Tree[rt].flag) Tree[rt].len1=Tree[rt].vr-Tree[rt].vl;
        else if(Tree[rt].l+1==Tree[rt].r) Tree[rt].len1=0;
        else Tree[rt].len1=Tree[rt<<1].len1+Tree[rt<<1|1].len1;
        
        if(Tree[rt].flag>1) Tree[rt].len2=Tree[rt].vr-Tree[rt].vl;
        else if(Tree[rt].l+1==Tree[rt].r) Tree[rt].len2=0;
        else if(Tree[rt].flag==1) Tree[rt].len2=Tree[rt<<1].len1+Tree[rt<<1|1].len1;
        else Tree[rt].len2=Tree[rt<<1].len2+Tree[rt<<1|1].len2;

        if(Tree[rt].flag>2) Tree[rt].len3=Tree[rt].vr-Tree[rt].vl;
        else if(Tree[rt].l+1==Tree[rt].r) Tree[rt].len3=0;
        else if(Tree[rt].flag==2) Tree[rt].len3=Tree[rt<<1].len1+Tree[rt<<1|1].len1;
        else if(Tree[rt].flag==1) Tree[rt].len3=Tree[rt<<1].len2+Tree[rt<<1|1].len2;
        else Tree[rt].len3=Tree[rt<<1].len3+Tree[rt<<1|1].len3;
    }
    void Build(int l,int r,int rt,int A[]){
        Tree[rt].l=l;Tree[rt].r=r;
        Tree[rt].vl=A[l];Tree[rt].vr=A[r];
        Tree[rt].len1=Tree[rt].len2=Tree[rt].len3=0;
        Tree[rt].flag=0;
        if(l+1==r) return ;
        int mid=(l+r)>>1;
        Build(l,mid,rt<<1,A);Build(mid,r,rt<<1|1,A);
    }
    void Update(int ql,int qr,int val,int rt){
        if(ql<=Tree[rt].vl&&Tree[rt].vr<=qr){
            Tree[rt].flag+=val;PushUp(rt);
            return ;
        }
        if(qr<=Tree[rt<<1].vr) Update(ql,qr,val,rt<<1);
        else if(ql>=Tree[rt<<1|1].vl) Update(ql,qr,val,rt<<1|1);
        else{
            Update(ql,qr,val,rt<<1);
            Update(ql,qr,val,rt<<1|1);
        }PushUp(rt);
    }
};
struct Line{
    int x,y1,y2,z1,z2;int flag;
    friend int operator < (Line a,Line b){
        return a.xZ[j]){
                    Tmp[++Cnt]=X[i];
                }
            }
            for(int i=1;i<=Cnt;++i){//        ，  Y
                Seg.Update(Tmp[i].y1,Tmp[i].y2,Tmp[i].flag,1);
                Area+=Seg.Tree[1].len3*(Tmp[i+1].x-Tmp[i].x);
            }
            Ans+=Area*(Z[j+1]-Z[j]);
        }printf("Case %d: %lld
",Case++,Ans);
    }
}
/*
2
1
0 0 0 5 6 4
3
0 0 0 5 5 5
3 3 3 9 10 11
3 3 3 13 20 45
*/
nodejsメモ7(グローバルオブジェクト)