分别求出7种颜色覆盖的面积。
做法：每种颜色设定一个标号，以二进制表示R：100 G：010 B：001 。这样很明显可以知道RG：110 GB：011 以此类推。
求解时，需要开一个二维标记数组，标记了这一段的某种颜色被标记了几次，然后类似状压的方式求解。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define N 41010
#define LL __int64
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
map<int,int>f;
int s[N<<][];
int fs[N<<],a[N],ff[N<<][];
int val[N];
int id[];
LL num[N];
struct node
{
int x1,x2,y;
int f;
node(){}
node(int x1,int x2,int y,int f):x1(x1),x2(x2),y(y),f(f){}
bool operator <(const node &S)const
{
return y<S.y;
}
}p[N];
void up(int w,int l,int r)
{
int i;
if(fs[w]==)
{
for(i = ; i <= ; i++)
{
if(l==r)
s[w][i] = ;
else
s[w][i] = s[w<<][i]+s[w<<|][i];
}
}
else
{
int res = val[r+]-val[l];
int cnt[] = {};
for(i = ; i <= ; i++)
{
if(l==r)
{
if(i==fs[w])
cnt[i] += val[r+]-val[l];
else
cnt[i] += ;
}
else
{
cnt[i|fs[w]] += s[w<<][i]+s[w<<|][i];
}
}
for(i = ; i <= ; i++)
res-=cnt[i];
cnt[fs[w]]+=res;
for(i = ; i <= ; i++)
s[w][i] = cnt[i];
}
}
void build(int l,int r,int w)
{
int i;
for(i = ;i<= ; i++)
{s[w][i] = ff[w][i] = ;}
fs[w] = ;
if(l==r)
{
return ;
}
int m = (l+r)>>;
build(l,m,w<<);
build(m+,r,w<<|);
}
void update(int a,int b,int d,int l,int r,int w)
{
if(a<=l&&b>=r)
{
ff[w][abs(d)]+=d/abs(d);
if(d>)
fs[w]|=d;
else if(ff[w][-d]==) fs[w]+=d;
up(w,l,r);
return ;
}
int m = (l+r)>>;
if(a<=m) update(a,b,d,l,m,w<<);
if(b>m) update(a,b,d,m+,r,w<<|);
up(w,l,r);
}
int main()
{
id['R'] = ;
id['G'] = ;
id['B'] = ;
int i,j,t,n,cas = ;
char sr[];
cin>>t;
while(t--)
{
f.clear();
scanf("%d",&n);
memset(num,,sizeof(num));
int g= ,dd[];
for(i = ; i <= n; i++)
{
int x1,x2,y1,y2,k;
scanf("%s%d%d%d%d",sr,&x1,&y1,&x2,&y2);
if(sr[]=='R') k = id['R'];
else if(sr[]=='G') k = id['G'];
else k = id['B'];
p[++g] = node(x1,x2,y1,k);
a[g] = x1;
p[++g] = node(x1,x2,y2,-k);
a[g] = x2;
}
sort(a+,a+g+);
sort(p+,p+g+);
int o = ;
f[a[]] = ++o;
val[o] = a[];
for(i = ; i <= g ; i++)
if(a[i]!=a[i-])
{
f[a[i]] = ++o;
val[o] = a[i];
}
build(,o-,); for(i = ; i < g; i++)
{
int l = f[p[i].x1];
int r = f[p[i].x2]-; //cout<<l<<" "<<r<<endl;
if(l<=r)
{
update(l,r,p[i].f,,o-,);
}
for(j = ; j <= ; j++)
num[j] += (LL)(p[i+].y-p[i].y)*s[][j];
}
dd[] = ,dd[] = ,dd[] = ,dd[] = ,dd[] = ,dd[] = ,dd[] = ;
printf("Case %d:\n",cas++);
for(i = ; i <= ; i++)
printf("%I64d\n",num[dd[i]]);
}
return ;
}