对于这类面积覆盖的题，大致就两点要注意的
1.同一把矩形放在笛卡尔坐标系上做
2.pushup函数要注意下细节:及在统计子区间和之前要先判断是否有子区间
用sum数组来保存区间被覆盖的情况，如果遇到多次覆盖问题，那就开多个sum数组分别保存被覆盖n次的情况
用cnt数组保存区间被完全覆盖的次数，如果是不同类型的矩形需要分别统计或者有特殊要求，那就开多个cnt数组分别保存
pushup如果cnt[rt]超过了k次，满足要求，那么就直接把sum[k]赋值为当前区间长度，然后其他sum数组归零，结束返回
否则如果cnt[rt]不为0，先把所有该区间的sum置零，然后把覆盖了该区间cnt[rt]次对应的sum赋值为当前区间长度如果rt没有子区间就返回，有子区间 i 就从1循环到k，如果cnt[rt]+i>=k,那么对应的sum[k]就是两个子区间的被覆盖i次的长度和，否则sum[i+cnt[rt]]就是两个子区间被覆盖i次的和。结束这次循环后sum[cnt[rt]]还要再减去本区间被覆盖大于cnt[rt]次对应的sum
最后如果cnt[rt]=0，i从1到k循环，如果没有子区间，sum就是0，有的话就是子区间的和
/* 颜色覆盖，多了颜色融合，， 用七个sum去记录七种颜色，三个cnt记录三种不同颜色的覆盖 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<map> using namespace std; #define maxn 20005 #define lson l,m,rt<<1 #define rson m,r,rt<<1|1 #define ll long long struct Seg{ int x,y1,y2,c; Seg(){} Seg(int a,int b,int c,int d):x(a),y1(b),y2(c),c(d){} bool operator<(const Seg & a)const {return x<a.x;} }segs[maxn]; int y[maxn],toty,tot; int sum[maxn<<2][8],cnt[maxn<<2][4]; map<int,int>mp; void pushup(int rt,int l,int r){ int tmp=0; if(cnt[rt][1]) tmp|=1; if(cnt[rt][2]) tmp|=2; if(cnt[rt][3]) tmp|=4; //cout << tmp << endl; for(int i=0;i<=7;i++) sum[rt][i]=0; if(tmp){ sum[rt][tmp]=y[r]-y[l]; for(int i=1;i<=7;i++) if(l+1!=r && tmp!=(tmp|i)){ //如果有更高级的颜色 sum[rt][tmp|i]+=sum[rt<<1][i]+sum[rt<<1|1][i]; sum[rt][tmp]-=sum[rt<<1][i]+sum[rt<<1|1][i]; } } else if(l+1!=r) for(int i=1;i<=7;i++) sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][i]; } void update(int L,int R,int c,int l,int r,int rt){ if(L<=l && R>=r){ //cout<<c<<endl; if(c>0) cnt[rt][c]+=1; else cnt[rt][-c]-=1; 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=0; mp.clear(); memset(sum,0,sizeof sum); memset(cnt,0,sizeof cnt); } int main(){ int T,x1,x2,y1,y2,c,n; char col[5]; cin >> T; for(int tt=1;tt<=T;tt++){ init(); scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%s%d%d%d%d",col,&x1,&y1,&x2,&y2); if(col[0]=='R') c=1; if(col[0]=='G') c=2; if(col[0]=='B') c=3; segs[tot++]=Seg(x1,y1,y2,c); segs[tot++]=Seg(x2,y1,y2,-c); y[toty++]=y1,y[toty++]=y2; } sort(y,y+toty); toty=unique(y,y+toty)-y; for(int i=0;i<toty;i++) mp[y[i]]=i; sort(segs,segs+tot); ll res[8]={}; for(int i=0;i<tot;i++){ if(i!=0){ for(int j=1;j<=7;j++) res[j]+=(ll)(segs[i].x-segs[i-1].x)*sum[1][j]; } int y1=mp[segs[i].y1]; int y2=mp[segs[i].y2]; update(y1,y2,segs[i].c,0,toty-1,1); } printf("Case %d:\n",tt); printf("%lld\n",res[1]); printf("%lld\n",res[2]); printf("%lld\n",res[4]); printf("%lld\n",res[3]); printf("%lld\n",res[5]); printf("%lld\n",res[6]); printf("%lld\n",res[7]); } return 0; }
转载于:https://www.cnblogs.com/zsben991126/p/9968122.html
相关资源：各显卡算力对照表！