本文共 1641 字，大约阅读时间需要 5 分钟。
手贱把i打成j，调了半天
/*面积并转体积并，长方体高度为作物价格算体积并：在笛卡尔坐标系的y轴上建立线段树cnt记录区间被完全覆盖的次数，sum记录区间被覆盖的总长度 以平行于xoy的平面从下往上扫描，把穿过扫描面的长方体的上下边加入集合segs,对集合segs里的边排序，然后一根扫描线从下往上扫描另外，更新是不影响线段边界的 */#include #include #include #include #include #define ll long long #define maxn 30000*2+10#define lson l,m,rt<<1#define rson m,r,rt<<1|1using 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 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,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 =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
转载于:https://www.cnblogs.com/zsben991126/p/9960754.html