立方体交，自己写的莫名其妙MLE了，不知道为什么
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define maxn 2010 using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ll long long 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]; struct seg{//水平横线段 int l,r,h,d; seg(){} seg(int l,int r,int h,int d):l(l),r(r),h(h),d(d){} bool operator<(const seg & a)const { return h<a.h; } }segs[maxn]; int tots; int y[maxn],z[maxn],tot,toty,totz;//y轴，z轴上的数据 int len1[maxn<<2],len2[maxn<<2],len3[maxn<<2];//线段树区间被覆盖了1，2，3次的长度 int cnt[maxn<<2];//区间被完全覆盖的次数 inline void pushup(int rt,int l,int r){ if(cnt[rt]>=3){ len3[rt]=y[r+1]-y[l]; len2[rt]=len1[rt]=0; } else if(cnt[rt]==2){ len1[rt]=0; len2[rt]=y[r+1]-y[l]; if(l==r) len3[rt]=0;//没有子区间的情况 else { len3[rt]=len3[rt<<1]+len3[rt<<1|1]+len2[rt<<1]+len2[rt<<1|1]+len1[rt<<1]+len1[rt<<1|1]; len2[rt]-=len3[rt]; } } else if(cnt[rt]==1){ len1[rt]=y[r+1]-y[l]; if(l==r) len3[rt]=len2[rt]=0;//没有子区间的情况 else { len3[rt]=len3[rt<<1]+len3[rt<<1|1]+len2[rt<<1]+len2[rt<<1|1]; len2[rt]=len1[rt<<1]+len1[rt<<1|1]; len1[rt]-=len2[rt]+len3[rt]; } } else {//cnt[rt]==0 if(l==r) len3[rt]=len2[rt]=len1[rt]=0; else { len3[rt]=len3[rt<<1]+len3[rt<<1|1]; len2[rt]=len2[rt<<1]+len2[rt<<1|1]; len1[rt]=len1[rt<<1]+len1[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); } void init(){ tot=toty=totz=tots=0; memset(y,0,sizeof y); memset(z,0,sizeof z); memset(len1,0,sizeof len1); memset(len2,0,sizeof len2); memset(len3,0,sizeof len3); memset(cnt,0,sizeof cnt); } int main(){ int T,n; scanf("%d",&T); for(int tt=1;tt<=T;tt++){ init(); scanf("%d",&n); for(int i=1;i<=n;i++){ int a,b,c,d,e,f; scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f); cubes[i]=cube(a,b,c,d,e,f); y[tot]=b;z[tot++]=c; y[tot]=e;z[tot++]=f; } if(n<3) {puts("0");continue;} sort(y,y+tot);toty=unique(y,y+tot)-y; sort(z,z+tot);totz=unique(z,z+tot)-z; ll res=0; for(int i=0;i<totz-1;i++){ tots=0; for(int j=1;j<=n;j++) if(cubes[j].z1<=z[i] && cubes[j].z2>=z[i+1]){ segs[tots++]=seg(cubes[j].x1,cubes[j].x2,cubes[j].y1,1); segs[tots++]=seg(cubes[j].x1,cubes[j].x2,cubes[j].y2,-1); } sort(segs,segs+tots);//将水平横线段排序 for(int j=0;j<tots;j++){//将这些边更新到线段树中 if(j!=0) res+=(z[i+1]-z[i])*(segs[j].h-segs[j-1].h)*len3[1]; int L=lower_bound(y,y+toty,segs[j].l)-y; int R=lower_bound(y,y+toty,segs[j].r)-y-1; update(L,R,segs[j].d,0,toty,1);//为什么要计算在前更新在后？ } } printf("%lld\n",res); } return 0; }kuangbin的板子是可以过的。。
转载于:https://www.cnblogs.com/zsben991126/p/9948947.html
