题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4419
题目大意：给你n个矩形，每个矩形都有一种颜色，矩形覆盖会出现另外一种颜色，问你所有矩形中不同的颜色各出现的面积。
解题思路：开始一直只用一个标记，1,2,4，处理来处理去发现一直搞不来。最后用两个标记，一个存+1，-1，和普通面积并类似，另外开一个三位的标记数组，0位表示'R'，1位表示‘G’,2位表示‘B’，sum数组要开8个状态（和8颗线段树思想类似），每次处理到当前节点时，该节点所有sum值清0（叶子节点的sum[u][0]表示的就是区间长度，要进行预先建树），根据自己当前的状态再由孩子传递数值上来进行更新操作。这题很巧妙的用到了或运算，表示我开始没想到，发散性思维 O.O。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define lz 2*u,l,mid
#define rz 2*u+1,mid+1,r
typedef long long lld;
const int maxn=;
lld sum[*maxn][];
int flag[*maxn][];
int X[maxn];
lld ans[]; struct Node
{
int lx, rx, y;
int c, s;
Node() {};
Node(int lx_, int rx_, int y_, int c_, int s_)
{
lx=lx_, rx=rx_, y=y_, c=c_, s=s_;
}
bool operator <(const Node &S) const
{
if(y==S.y) return s>S.s;
else return y<S.y;
}
} line[maxn]; int find(int tmp, int n)
{
int l=, r=n, mid;
while(l<=r)
{
mid=(l+r)>>;
if(X[mid]==tmp) return mid;
else if(X[mid]<tmp) l=mid+;
else r=mid-;
}
} void push_up(int u, int l, int r)
{
int state=;
for(int i=; i<=; i++) if(flag[u][i]) state|=(<<i);
memset(sum[u],,sizeof(sum[u]));
if(l==r) sum[u][state]=X[r+]-X[l];
else
{
for(int i=; i<; i++)
sum[u][state|i]+=sum[*u][i]+sum[*u+][i];
}
} void build(int u, int l, int r)
{
memset(sum[u],,sizeof(sum[u]));
memset(flag[u],,sizeof(flag[u]));
if(l==r)
{
sum[u][]=X[r+]-X[l];
return ;
}
int mid=(l+r)>>;
build(lz);
build(rz);
sum[u][]=sum[*u][]+sum[*u+][];
} void Update(int u, int l, int r, int tl, int tr, int s, int c)
{
if(tl>tr) return ;
if(tl<=l&&r<=tr)
{
flag[u][s]+=c;
push_up(u,l,r);
return ;
}
int mid=(l+r)>>;
if(tr<=mid) Update(lz,tl,tr,s,c);
else if(tl>mid) Update(rz,tl,tr,s,c);
else
{
Update(lz,tl,mid,s,c);
Update(rz,mid+,tr,s,c);
}
push_up(u,l,r);
} int main()
{
int n, T, tcase=;
cin >> T;
while(T--)
{
cin >> n;
int num=;
memset(flag,,sizeof(flag));
memset(sum,,sizeof(sum));
memset(ans,,sizeof(ans));
for(int i=; i<n; i++)
{
int x1,x2,y1,y2, s;
char ch[];
scanf("%s%d%d%d%d",ch,&x1,&y1,&x2,&y2);
if(ch[]=='R') s=;
else if(ch[]=='G') s=;
else s=;
line[++num]=Node(x1,x2,y1,s,);
X[num]=x1;
line[++num]=Node(x1,x2,y2,s,-);
X[num]=x2;
}
sort(X+,X+num+);
sort(line+,line+num+);
int k=;
for(int i=; i<=num; i++)
if(X[i]!=X[i+]) X[++k]=X[i];
build(,,k);
for(int i=; i<num; i++)
{
int l=find(line[i].lx,k);
int r=find(line[i].rx,k)-;
Update(,,k,l,r,line[i].c,line[i].s);
for(int j=; j<=; j++)
ans[j]+=sum[][j]*(line[i+].y-line[i].y);
}
printf("Case %d:\n",++tcase);
swap(ans[],ans[]);
for(int i=; i<=; i++) cout << ans[i] <<endl;
}
return ;
}