HDU4419Colourful Rectangle解题报告

又一道矩形面积并，只要要统计七种颜色分别的面积，所以在线段树里维护一个颜色数组，一个各种颜色覆盖长度的数组，其余的和求矩形面积并就很类似了
View Code
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #define N 10005
  6 #define L(x) (x<<1)
  7 #define R(x) (x<<1|1)
  8 using namespace std;
  9 typedef long long LL;
 10 struct Line
 11 {
 12     LL x,y1,y2;
 13     LL l,c;
 14     friend bool operator<(Line a,Line b)
 15     {
 16         return a.x<b.x;
 17     }
 18 };
 19 Line line[N*4];
 20 LL n;
 21 LL y[N*4];
 22 struct node
 23 {
 24     LL l,r;
 25     LL c[3],s[8];
 26 };
 27 node tree[N*4];
 28 void build(LL id,LL l,LL r)
 29 {
 30     tree[id].l=l;
 31     tree[id].r=r;
 32     memset(tree[id].c,0,sizeof(tree[id].c));
 33     memset(tree[id].s,0,sizeof(tree[id].s));
 34     tree[id].s[0]=y[tree[id].r]-y[tree[id].l];
 35     if(l+1>=r)
 36     return;
 37     LL mid=(l+r)>>1;
 38     build(L(id),l,mid);
 39     build(R(id),mid,r);
 40 }
 41 void sum(LL u)
 42 {
 43     LL st=0;
 44     LL i;
 45     for(i=0;i<3;i++)
 46     if(tree[u].c[i])
 47     st|=(1<<i);
 48     memset(tree[u].s,0,sizeof(tree[u].s));
 49     if(tree[u].l+1==tree[u].r)
 50     {
 51         tree[u].s[st]=y[tree[u].r]-y[tree[u].l];
 52     }
 53     else
 54     {
 55         for(i=0;i<8;i++)
 56         {
 57             tree[u].s[i|st]+=tree[L(u)].s[i]+tree[R(u)].s[i];
 58         }
 59     }
 60 }
 61 void update(LL u,LL l,LL r,LL col,LL c)
 62 {
 63     if(tree[u].l==l&&tree[u].r==r)
 64     {
 65         tree[u].c[col]+=c;
 66         sum(u);
 67         return;
 68     }
 69     LL mid=(tree[u].l+tree[u].r)>>1;
 70     if(r<=mid)
 71     update(L(u),l,r,col,c);
 72     else if(l>=mid)
 73     update(R(u),l,r,col,c);
 74     else
 75     {
 76         update(L(u),l,mid,col,c);
 77         update(R(u),mid,r,col,c);
 78     }
 79     sum(u);
 80 }
 81 LL search(LL x)
 82 {
 83     LL low=1,high=n,mid;
 84     while(low<=high)
 85     {
 86         mid=(low+high)>>1;
 87         if(y[mid]==x)
 88         return mid;
 89         if(y[mid]>x)
 90         high=mid-1;
 91         else
 92         low=mid+1;
 93     }
 94     return mid;
 95 }
 96 LL color(char *s)
 97 {
 98     if(s[0]=='R')
 99     return 0;
100     if(s[0]=='G')
101     return 1;
102     return 2;
103 }
104 int main()
105 {
106     LL ans[8],i,j,k,l,r,c;
107     LL lnum,x1,y1,x2,y2,lsum;
108     char s[3];
109     LL tcase,icase=0;
110     scanf("%I64d",&tcase);
111     while(tcase--)
112     {
113         scanf("%I64d",&lnum);
114         lsum=1;
115         for(i=0;i<lnum;i++)
116         {
117             scanf("%s%I64d%I64d%I64d%I64d",s,&x1,&y1,&x2,&y2);
118             c=color(s);
119             y[lsum]=y1;
120             line[lsum].x=x1;
121             line[lsum].y1=y1;
122             line[lsum].y2=y2;
123             line[lsum].c=c;
124             line[lsum].l=1;
125             lsum++;
126             y[lsum]=y2;
127             line[lsum].x=x2;
128             line[lsum].y1=y1;
129             line[lsum].y2=y2;
130             line[lsum].c=c;
131             line[lsum].l=-1;
132             lsum++;
133         }
134         sort(y+1,y+lsum);
135         sort(line+1,line+lsum);
136         n=unique(y+1,y+lsum)-(y+1);
137         build(1,1,n);
138         memset(ans,0,sizeof(ans));
139         for(i=1;i<lsum-1;i++)
140         {
141             l=search(line[i].y1);
142             r=search(line[i].y2);
143             update(1,l,r,line[i].c,line[i].l);
144             for(j=1;j<=7;j++)
145             {
146                 ans[j]+=(tree[1].s[j]*(line[i+1].x-line[i].x));
147             }
148         }
149         printf("Case %I64d:\n",++icase);
150         for(i=1;i<=7;i++)
151         if(i!=3&&i!=4)
152         printf("%I64d\n",ans[i]);
153         else if(i==3)
154         printf("%I64d\n",ans[4]);
155         else
156         printf("%I64d\n",ans[3]);
157     }
158     return 0;
159 }