题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4419
解析:跟一般矩形面积并有一点的区别,就是每条线的状态要用一个数组来维护,这里的depth[ i ] 表示当前状态第i中颜色的已覆盖的长度,三种基本颜色可以分别用1,2,4表示,然后通过二进制运算得到其他颜色的标号,其他也没什么了。
参考代码:
#include<iostream> #include<algorithm> #include<string.h> #include<iomanip> #include<stdio.h> #include<math.h> using namespace std; #define clr(arr,val) memset(arr,val,sizeof(arr)) const int M = 20500; enum In{lt,rt}; int Out[8] = {0,1,2,4,3,5,6,7}; int n,k; int num_y[M*2]; struct rectangle{ int colour; int x1,y1,x2,y2; }rec[M]; struct SegTree{ int count[8]; int L,R; long long depth[8]; }Tree[M*8]; void Update(int); void Build(int root,int L,int R){ clr(Tree[root].count,0); Tree[root].L = L; Tree[root].R = R; if(L == R - 1) return ; Build(root<<1,L,(L+R)/2); Build((root<<1)+1,(L+R)/2,R); } void Insert(int root,int L,int R,int colour){ if(num_y[ Tree[root].L ] >= L && num_y[ Tree[root].R ] <= R){ Tree[root].count[colour]++; Update(root); } else { if(L < num_y[ (Tree[root].L+Tree[root].R)/2 ]){ Insert(root<<1,L,R,colour); Update(root); } if(R > num_y[ (Tree[root].L+Tree[root].R)/2 ]){ Insert((root<<1)+1,L,R,colour); Update(root); } } } void Delete(int root,int L,int R,int colour){ if(num_y[ Tree[root].L ] >= L && num_y[ Tree[root].R ] <= R){ Tree[root].count[colour]--; Update(root); } else { if(L < num_y[ (Tree[root].L+Tree[root].R)/2 ]){ Delete(root<<1,L,R,colour); Update(root); } if(R > num_y[ (Tree[root].L+Tree[root].R)/2 ]){ Delete((root<<1)+1,L,R,colour); Update(root); } } } void Update(int root){ clr(Tree[root].depth,0); int colour = (Tree[root].count[1]>0?1:0) | (Tree[root].count[2]>0?2:0) | (Tree[root].count[4]>0?4:0); if(colour > 0){ Tree[root].depth[colour] += num_y[ Tree[root].R ] - num_y[ Tree[root].L ]; for(int i = 1;i != 8;++i){ if((i | colour) != colour){ int tmp = Tree[root<<1].depth[i] + Tree[(root<<1)+1].depth[i]; Tree[root].depth[colour] -= tmp; Tree[root].depth[i|colour] += tmp; } } } else if(Tree[root].L != Tree[root].R - 1) { for(int i = 1;i != 8;++i) Tree[root].depth[i] = Tree[root<<1].depth[i] + Tree[(root<<1)+1].depth[i]; } } struct operation{ In in; int x,lower_y,high_y,colour; }Event[M*4]; void input(){ cin>>n; char ch; for(int i = 0;i != n;++i){ cin>>ch>>rec[i].x1>>rec[i].y1>>rec[i].x2>>rec[i].y2; if(ch == 'R') rec[i].colour = 1; if(ch == 'G') rec[i].colour = 2; if(ch == 'B') rec[i].colour = 4; } } void Hash(){ for(int i = 0;i != n;++i){ num_y[i*2] = rec[i].y1; num_y[i*2+1] = rec[i].y2; Event[i*2].in = lt; Event[i*2].x = rec[i].x1; Event[i*2].lower_y = rec[i].y1; Event[i*2].high_y = rec[i].y2; Event[i*2].colour = rec[i].colour; Event[i*2+1].in = rt; Event[i*2+1].x = rec[i].x2; Event[i*2+1].lower_y = rec[i].y1; Event[i*2+1].high_y = rec[i].y2; Event[i*2+1].colour = rec[i].colour; } sort(num_y,num_y+n*2); } bool cmp(operation a,operation b){ return a.x < b.x; } void solve(){ input(); Hash(); Build(1,0,n*2-1); sort(Event,Event+n*2,cmp); long long ans[8],depth[8]; clr(ans,0); clr(depth,0); for(int i = 0;i < n*2;++i){ if(Event[i].in == lt) Insert(1,Event[i].lower_y,Event[i].high_y,Event[i].colour); else Delete(1,Event[i].lower_y,Event[i].high_y,Event[i].colour); for(int j = 1;j != 8;++j){ ans[j] += (long long)depth[j] * (long long)(i?(Event[i].x-Event[i-1].x):0); } memcpy(depth,Tree[1].depth,sizeof(Tree[1].depth)); } cout<<"Case "<<++k<<":"<<endl; for(int i = 1;i != 8;++i){ cout<<ans[ Out[i] ]<<endl; } } int main(){ k = 0; int T; cin>>T; while(T--){ solve(); } return 0; }