昌平网站制作公司,重庆城乡建设网站,学校网站建设预算,河南天丰建设工程有限公司网站对于这类面积覆盖的题#xff0c;大致就两点要注意的 1.同一把矩形放在笛卡尔坐标系上做 2.pushup函数要注意下细节:及在统计子区间和之前要先判断是否有子区间 用sum数组来保存区间被覆盖的情况#xff0c;如果遇到多次覆盖问题#xff0c;那就开多个sum数组分别保存被覆盖…对于这类面积覆盖的题大致就两点要注意的 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]ik,那么对应的sum[k]就是两个子区间的被覆盖i次的长度和否则sum[icnt[rt]]就是两个子区间被覆盖i次的和。结束这次循环后sum[cnt[rt]]还要再减去本区间被覆盖大于cnt[rt]次对应的sum 最后如果cnt[rt]0i从1到k循环如果没有子区间sum就是0有的话就是子区间的和 /*
颜色覆盖多了颜色融合
用七个sum去记录七种颜色三个cnt记录三种不同颜色的覆盖
*/
#includeiostream
#includecstring
#includecstdio
#includealgorithm
#includemap
using namespace std;
#define maxn 20005
#define lson l,m,rt1
#define rson m,r,rt1|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 xa.x;}
}segs[maxn];
int y[maxn],toty,tot;
int sum[maxn2][8],cnt[maxn2][4];
mapint,intmp;
void pushup(int rt,int l,int r){int tmp0;if(cnt[rt][1]) tmp|1;if(cnt[rt][2]) tmp|2;if(cnt[rt][3]) tmp|4;
//cout tmp endl;for(int i0;i7;i)sum[rt][i]0;if(tmp){sum[rt][tmp]y[r]-y[l];for(int i1;i7;i)if(l1!r tmp!(tmp|i)){ //如果有更高级的颜色sum[rt][tmp|i]sum[rt1][i]sum[rt1|1][i];sum[rt][tmp]-sum[rt1][i]sum[rt1|1][i];}}else if(l1!r) for(int i1;i7;i) sum[rt][i]sum[rt1][i]sum[rt1|1][i];
}
void update(int L,int R,int c,int l,int r,int rt){if(Ll Rr){
//coutcendl;if(c0) cnt[rt][c]1;else cnt[rt][-c]-1;pushup(rt,l,r);return;}int mlr1;if(Lm) update(L,R,c,lson);if(Rm) update(L,R,c,rson);pushup(rt,l,r);
}
void init(){tottoty0;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 tt1;ttT;tt){init();scanf(%d,n);for(int i0;in;i){scanf(%s%d%d%d%d,col,x1,y1,x2,y2);if(col[0]R) c1;if(col[0]G) c2;if(col[0]B) c3;segs[tot]Seg(x1,y1,y2,c);segs[tot]Seg(x2,y1,y2,-c);y[toty]y1,y[toty]y2;}sort(y,ytoty);totyunique(y,ytoty)-y;for(int i0;itoty;i) mp[y[i]]i;sort(segs,segstot);ll res[8]{};for(int i0;itot;i){if(i!0){for(int j1;j7;j)res[j](ll)(segs[i].x-segs[i-1].x)*sum[1][j];}int y1mp[segs[i].y1];int y2mp[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
