hdu3255扫描线：带权面积交转体积交

手贱把i打成j，调了半天

/*

面积并转体积并，长方体高度为作物价格

算体积并：在笛卡尔坐标系的y轴上建立线段树cnt记录区间被完全覆盖的次数，sum记录区间被覆盖的总长度

         以平行于xoy的平面从下往上扫描，把穿过扫描面的长方体的上下边加入集合segs,对集合segs里的边排序，然后一根扫描线从下往上扫描

另外，更新是不影响线段边界的

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<map>

#define ll long long

#define maxn 30000*2+10

#define lson l,m,rt<<1

#define rson m,r,rt<<1|1

using namespace std;

struct Seg{

    int l,r,h,c;

    Seg(){}

    Seg(int a,int b,int c,int d):l(a),r(b),h(c),c(d){}

    bool operator<(const Seg & a)const{

        return h<a.h;

    }

}segs[maxn];

struct cube{

    int x1,y1,z1,x2,y2,z2;

    cube(){}

    cube(int a,int b,int c,int d,int e,int f):x1(a),y1(b),z1(c),x2(d),y2(e),z2(f){}

}cubes[maxn];

int seeds[],n,m;

int y[maxn<<],toty,tot;

int z[maxn],totz;

map<int,int>mp;

ll cnt[maxn<<],len[maxn<<];

void init(){

    tot=toty=totz=;

    mp.clear();

    memset(cnt,,sizeof cnt);

    memset(len,,sizeof len);

}

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

    if(cnt[rt]){

        len[rt]=y[r]-y[l];

    }

    else if(l+==r) len[rt]=;

    else len[rt]=len[rt<<]+len[rt<<|];

}

void update(int L,int R,int c,int l,int r,int rt){

    if(L<=l && R>=r){

        cnt[rt]+=c;

        pushup(rt,l,r);

        return;

    }

    int m=l+r>>;

    if(L<m) update(L,R,c,lson);

    if(R>m) update(L,R,c,rson);

    pushup(rt,l,r);

}

int main(){

    int T,a,b,c,d,e;

    cin >> T;

    for(int tt=;tt<=T;tt++){

        init();

        cin >> n >> m;

        for(int i=;i<=m;i++)scanf("%d",&seeds[i]);

        z[tot++]=;//把地平线加上！

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

            scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);

            cubes[i]=cube(a,b,,c,d,seeds[e]);

            z[totz++]=seeds[e];

            y[toty++]=b;y[toty++]=d;

        }

        z[totz++]=;

        sort(z,z+totz);totz=unique(z,z+totz)-z;//离散化z轴

        sort(y,y+toty);toty=unique(y,y+toty)-y;//离散化x轴

        for(int i=;i<toty;i++) mp[y[i]]=i;

        ll res=;

        for(int i=;i<totz-;i++){

            tot=;//初始化

            memset(segs,,sizeof segs);

           /* memset(cnt,0,sizeof cnt);

            memset(len,0,sizeof len); */

            for(int j=;j<=n;j++){//遍历所有cubes，把符合条件的加进去

                if(cubes[j].z1<=z[i] && cubes[j].z2>=z[i+]){

                    segs[tot++]=Seg(cubes[j].y1,cubes[j].y2,cubes[j].x1,);

                    segs[tot++]=Seg(cubes[j].y1,cubes[j].y2,cubes[j].x2,-);

                }

            }

            sort(segs,segs+tot);

            for(int j=;j<tot;j++){

                if(j!=)

                    res+=(ll)(z[i+]-z[i])*(segs[j].h-segs[j-].h)*len[];

                update(mp[segs[j].l],mp[segs[j].r],segs[j].c,,toty-,);

            }

        }

        printf("Case %d: %lld\n",tt,res);

    }

    return ;

}