首页 > 代码库 > HDU 4419 Colourful Rectangle --离散化+线段树扫描线
HDU 4419 Colourful Rectangle --离散化+线段树扫描线
题意： 有三种颜色的矩形n个，不同颜色的矩形重叠会生成不同的颜色，总共有R,G,B,RG,RB,GB,RGB 7种颜色，问7种颜色每种颜色的面积。
解法： 很容易想到线段树扫描线求矩形面积并，但是如何维护每种颜色的长度着实让我伤透了脑筋。后来看了一位朋友的题解，才幡然醒悟。
开始想到了用二进制表示颜色，R用001表示，G用010表示，B用100表示。那么就可以用十进制1~7表示7种不同颜色了。
维护 cov[rt][1~3] 表示此区间内3种原色各有多少个， Len[rt][i]表示每种颜色的长度。
重点是pushup的写法，详情见代码， 离散化什么还比较简单。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define lll __int64using namespace std;#define N 10107lll Len[7*N][8];int cov[7*N][4];struct Line{ int y1,y2,x; int col;}line[2*N];int yy[2*N];int cmp(Line ka,Line kb) { return ka.x < kb.x; }void pushup(int l,int r,int rt){ int state = 0; for(int i=1;i<=3;i++) if(cov[rt][i]) state |= (1<<(i-1)); //表示此区间内有的颜色 for(int i=0;i<8;i++) Len[rt][i] = 0; //加了一层，要重新算各个颜色的长度 if(l+1 == r) //叶子节点 { Len[rt][state] = yy[r]-yy[l]; //只有此颜色state，长度为yy[r]-yy[l] return; } for(int i=0;i<8;i++) //否则使用下面的更新 Len[rt][i|state] += Len[2*rt][i] + Len[2*rt+1][i];}void build(int l,int r,int rt){ for(int i=1;i<=3;i++) cov[rt][i] = 0; for(int i=1;i<8;i++) Len[rt][i] = 0; Len[rt][0] = yy[r]-yy[l]; if(l == r-1) return; int mid = (l+r)/2; build(l,mid,2*rt); build(mid,r,2*rt+1);}void update(int l,int r,int aa,int bb,int cover,int rt){ if(aa <= l && bb >= r) { if(cover > 0) cov[rt][cover]++; else cov[rt][-cover]--; pushup(l,r,rt); return; } if(l+1 == r) return; int mid = (l+r)/2; if(aa <= mid) update(l,mid,aa,bb,cover,2*rt); if(bb > mid) update(mid,r,aa,bb,cover,2*rt+1); pushup(l,r,rt);}int main(){ int n,m,t,cs = 1,i,j; int x1,y1,x2,y2,c; char ss[4]; scanf("%d",&t); while(t--) { m = 1; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s%d%d%d%d",ss,&x1,&y1,&x2,&y2); if(ss[0] == ‘R‘) c = 1; else if(ss[0] == ‘G‘) c = 2; else c = 3; line[m].x = x1,line[m].y1 = y1,line[m].y2 = y2,line[m].col = c,yy[m++] = y1; line[m].x = x2,line[m].y1 = y1,line[m].y2 = y2,line[m].col = -c,yy[m++] = y2; } m--; sort(yy+1,yy+m+1); int cnt = 2; for(i=2;i<=m;i++) { if(yy[i] != yy[i-1]) yy[cnt++] = yy[i]; } cnt--; build(1,cnt,1); sort(line+1,line+m+1,cmp); lll ans[8]; memset(ans,0,sizeof(ans)); printf("Case %d:\n",cs++); for(i=1;i<m;i++) { int L = lower_bound(yy+1,yy+cnt+1,line[i].y1)-yy; int R = upper_bound(yy+1,yy+cnt+1,line[i].y2)-yy-1; update(1,cnt,L,R,line[i].col,1); for(j=1;j<8;j++) ans[j] += Len[1][j]*(line[i+1].x-line[i].x); } printf("%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n",ans[1],ans[2],ans[4],ans[3],ans[5],ans[6],ans[7]); } return 0;}
HDU 4419 Colourful Rectangle --离散化+线段树扫描线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。