手贱把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[4],n,m; int y[maxn<<2],toty,tot; int z[maxn],totz; map<int,int>mp; ll cnt[maxn<<2],len[maxn<<2]; void init(){ tot=toty=totz=0; mp.clear(); memset(cnt,0,sizeof cnt); memset(len,0,sizeof len); } inline void pushup(int rt,int l,int r){ if(cnt[rt]){ len[rt]=y[r]-y[l]; } else if(l+1==r) len[rt]=0; else len[rt]=len[rt<<1]+len[rt<<1|1]; } 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>>1; 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=1;tt<=T;tt++){ init(); cin >> n >> m; for(int i=1;i<=m;i++)scanf("%d",&seeds[i]); z[tot++]=0;//把地平线加上！ for(int i=1;i<=n;i++){ scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); cubes[i]=cube(a,b,0,c,d,seeds[e]); z[totz++]=seeds[e]; y[toty++]=b;y[toty++]=d; } z[totz++]=0; 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=0;i<toty;i++) mp[y[i]]=i; ll res=0; for(int i=0;i<totz-1;i++){ tot=0;//初始化 memset(segs,0,sizeof segs); /* memset(cnt,0,sizeof cnt); memset(len,0,sizeof len); */ for(int j=1;j<=n;j++){//遍历所有cubes，把符合条件的加进去 if(cubes[j].z1<=z[i] && cubes[j].z2>=z[i+1]){ segs[tot++]=Seg(cubes[j].y1,cubes[j].y2,cubes[j].x1,1); segs[tot++]=Seg(cubes[j].y1,cubes[j].y2,cubes[j].x2,-1); } } sort(segs,segs+tot); for(int j=0;j<tot;j++){ if(j!=0) res+=(ll)(z[i+1]-z[i])*(segs[j].h-segs[j-1].h)*len[1]; update(mp[segs[j].l],mp[segs[j].r],segs[j].c,0,toty-1,1); } } printf("Case %d: %lld ",tt,res); } return 0; }