HDU-4419-Colourful Rectangle(线段树) - c++编程基础

TOP

HDU-4419-Colourful Rectangle(线段树)

2015-07-20 17:37:08 来源: 作者: 【大中小】浏览:2次

Problem Description We use Red, Green and Blue to make new colours. See the picture below:

Now give you n rectangles, the colour of them is red or green or blue. You have calculate the area of 7 different colour. (Note: A region may be covered by same colour several times, but it’s final colour depends on the kinds of different colour)
Input The first line is an integer T(T <= 10), the number of test cases. The first line of each case contains a integer n (0 < n <= 10000), the number of rectangles. Then n lines follows. Each line start with a letter C(R means Red, G means Green, B means Blue) and four integers x1, y1, x2, y2(0 <= x1 < x2 < 10^9, 0 <= y1 < y2 < 10^9), the left-bottom"s coordinate and the right-top's coordinate of a rectangle.

Output For each case, output a line "Case a:", a is the case number starting from 1,then 7 lines, each line contain a integer, the area of each colour. (Note: You should print the areas as the order: R, G, B, RG, RB, GB, RGB).

Sample Input

Sample Output

Case 1:
3
3
0
1
0
0
0
Case 2:
4
4
12
4
4
4
4
Case 3:
0
12
15
0
0
0
0

Source 2012 ACM/ICPC Asia Regional Hangzhou Online
思路：维护区间R,G,B三种颜色的数量，更新时判断区间的组合颜色，再考虑与左右儿子的颜色组合的情况。

#include 
  
   
#include 
    #include 
    
      #include 
     
       using namespace std; map
      
       ii; struct S{ int r,g,b; int cr,cg,cb,crg,crb,cgb,crgb; }node[200000]; struct L{ int pos,l,r,type,flag; bool operator<(const L &p) const { return pos
       
        >1; build(idx<<1,s,mid); build(idx<<1|1,mid+1,e); } } void pop(int idx,int s,int e) { node[idx].cr=0; node[idx].cg=0; node[idx].cb=0; node[idx].crg=0; node[idx].crb=0; node[idx].cgb=0; node[idx].crgb=0; if(node[idx].r && node[idx].g && node[idx].b) { node[idx].crgb+=node[idx<<1].cr+node[idx<<1|1].cr; node[idx].crgb+=node[idx<<1].cg+node[idx<<1|1].cg; node[idx].crgb+=node[idx<<1].cb+node[idx<<1|1].cb; node[idx].crgb+=node[idx<<1].crg+node[idx<<1|1].crg; node[idx].crgb+=node[idx<<1].crb+node[idx<<1|1].crb; node[idx].crgb+=node[idx<<1].cgb+node[idx<<1|1].cgb; node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb; node[idx].crgb+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb; } if(!node[idx].r && node[idx].g && node[idx].b) { node[idx].crgb+=node[idx<<1].cr+node[idx<<1|1].cr; node[idx].cgb+=node[idx<<1].cg+node[idx<<1|1].cg; node[idx].cgb+=node[idx<<1].cb+node[idx<<1|1].cb; node[idx].crgb+=node[idx<<1].crg+node[idx<<1|1].crg; node[idx].crgb+=node[idx<<1].crb+node[idx<<1|1].crb; node[idx].cgb+=node[idx<<1].cgb+node[idx<<1|1].cgb; node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb; node[idx].cgb+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb; } if(node[idx].r && !node[idx].g && node[idx].b) { node[idx].crb+=node[idx<<1].cr+node[idx<<1|1].cr; node[idx].crgb+=node[idx<<1].cg+node[idx<<1|1].cg; node[idx].crb+=node[idx<<1].cb+node[idx<<1|1].cb; node[idx].crgb+=node[idx<<1].crg+node[idx<<1|1].crg; node[idx].crb+=node[idx<<1].crb+node[idx<<1|1].crb; node[idx].crgb+=node[idx<<1].cgb+node[idx<<1|1].cgb; node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb; node[idx].crb+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb; } if(node[idx].r && node[idx].g && !node[idx].b) { node[idx].crg+=node[idx<<1].cr+node[idx<<1|1].cr; node[idx].crg+=node[idx<<1].cg+node[idx<<1|1].cg; node[idx].crgb+=node[idx<<1].cb+node[idx<<1|1].cb; node[idx].crg+=node[idx<<1].crg+node[idx<<1|1].crg; node[idx].crgb+=node[idx<<1].crb+node[idx<<1|1].crb; node[idx].crgb+=node[idx<<1].cgb+node[idx<<1|1].cgb; node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb; node[idx].crg+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb; } if(node[idx].r && !node[idx].g && !node[idx].b) { node[idx].cr+=node[idx<<1].cr+node[idx<<1|1].cr; node[idx].crg+=node[idx<<1].cg+node[idx<<1|1].cg; node[idx].crb+=node[idx<<1].cb+node[idx<<1|1].cb; node[idx].crg+=node[idx<<1].crg+node[idx<<1|1].crg; node[idx].crb+=node[idx<<1].crb+node[idx<<1|1].crb; node[idx].crgb+=node[idx<<1].cgb+node[idx<<1|1].cgb; node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb; node[idx].cr+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb; } if(!node[idx].r && node[idx].g && !node[idx].b) { node[idx].crg+=node[idx<<1].cr+node[idx<<1|1].cr; node[idx].cg+=node[idx<<1].cg+node[idx<<1|1].cg; node[idx].cgb+=node[idx<<1].cb+node[idx<<1|1].cb; node[idx].crg+=node[idx<<1].crg+node[idx<<1|1].crg; node[idx].crgb+=node[idx<<1].crb+node[idx<<1|1].crb; node[idx].cgb+=node[idx<<1].cgb+node[idx<<1|1].cgb; node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb; node[idx].cg+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb; } if(!node[idx].r && !node[idx].g && node[idx].b) { node[idx].crb+=node[idx<<1].cr+node[idx<<1|1].cr; node[idx].cgb+=node[idx<<1].cg+node[idx<<1|1].cg; node[idx].cb+=node[idx<<1].cb+node[idx<<1|1].cb; node[idx].crgb+=node[idx<<1].crg+node[idx<<1|1].crg; node[idx].crb+=node[idx<<1].crb+node[idx<<1|1].crb; node[idx].cgb+=node[idx<<1].cgb+node[idx<<1|1].cgb; node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb; node[idx].cb+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb; } if(!node[idx].r && !node[idx].g && !node[idx].b)//别漏了这个 { node[idx].cr+=node[idx<<1].cr+node[idx<<1|1].cr; node[idx].cg+=node[idx<<1].cg+node[idx<<1|1].cg; node[idx].cb+=node[idx<<1].cb+node[idx<<1|1].cb; node[idx].crg+=node[idx<<1].crg+node[idx<<1|1].crg; node[idx].crb+=node[idx<<1].crb+node[idx<<1|1].crb; node[idx].cgb+=node[idx<<1].cgb+node[idx<<1|1].cgb; node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb; } } void update(int idx,int s,int e,int l,int r,int val,int flag) { if(l==s && r==e) { switch(val) { case 1:node[idx].r+=flag;break; case 2:node[idx].g+=flag;break; case 3:node[idx].b+=flag;break; } pop(idx,s,e); } else { int mid=(s+e)>>1; if(r<=mid) update(idx<<1,s,mid,l,r,val,flag); else if(l>mid) update(idx<<1|1,mid+1,e,l,r,val,flag); else { update(idx<<1,s,mid,l,mid,val,flag); update(idx<<1|1,mid+1,e,mid+1,r,val,flag); } pop(idx,s,e); } } int main() { int T,n,i,cnt,x1,y1,x2,y2,num,last,cases=1; long long ar,ag,ab,arg,arb,agb,argb; char s[5]; scanf("%d",&T); while(T--) { ii.clear(); ar=ag=ab=arg=arb=agb=argb=0; scanf("%d",&n); cnt=0; num=0; while(n--) { scanf("%s%d%d%d%d",s,&x1,&y1,&x2,&y2); if(!ii[y1]) lisan[num++]=y1,ii[y1]=1; if(!ii[y2]) lisan[num++]=y2,ii[y2]=1; line[cnt].pos=x1; line[cnt].l=y1; line[cnt].r=y2; line[cnt+1].pos=x2; line[cnt+1].l=y1; line[cnt+1].r=y2; if(s[0]=='R') { line[cnt].flag=1; line[cnt++].type=1; line[cnt].flag=-1; line[cnt++].type=1; } else if(s[0]=='G') { line[cnt].flag=1; line[cnt++].type=2; line[cnt].flag=-1; line[cnt++].type=2; } else { line[cnt].flag=1; line[cnt++].type=3; line[cnt].flag=-1; line[cnt++].type=3; } } sort(line,line+cnt); sort(lisan,lisan+num); for(i=0;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDOJ 4788 Hard Disk Drive	下一篇：截取屏幕并且保存到相册

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: