HDU - 4419 Colourful Rectangle （扫描线）

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

3
2
R 0 0 2 2
G 1 1 3 3 
3
R 0 0 4 4
G 2 0 6 4
B 0 2 6 6
3
G 2 0 3 8
G 1 0 6 1
B 4 2 7 7

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

题意：现在有红，绿，蓝三种颜色的矩阵，三种矩阵可以相互重叠，现在问你，重叠后，各颜色矩阵的面积是多少（可以说是很恶心的题了）。

题解：应该看题就能够想到用扫描线，但是维护起来却非常的困难。如果我们定义7个数组，应该可以，但是维护起来实在是麻烦。这里我们可以使用二进制来表示颜色红（1），绿（10），蓝（100）。现在我们我们就可以用1-7来表示7中颜色了，不同的颜色重叠，相当于该颜色的数字相“或”。例如：RG是红和绿重叠可以用3（1|2）表示。后面的每种颜色都可以这样子表示出来，然后就是维护了 ，我们直接用7个线段树来维护就好了。

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=2e4+5;
const int mod=10007;
const int inf=1e9;
const long long onf=1e18;
#define me(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI 3.141592653579323846
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll Hash[maxn<<1];
ll sum[maxn<<2][8];
int mark[maxn<<2][8],n;
ll ans[8];
struct node{
    int l,r,h,cnt,pos;
    node(int _l=0,int _r=0,int _h=0,int _cnt=0,int _pos=0):l(_l),r(_r),h(_h),cnt(_cnt),pos(_pos){}
    bool friend operator<(node a,node b){
        return a.h<b.h;
    }
}maps[maxn<<1];
void push_up(int l,int r,int rt){
    int flag=((mark[rt][1]?1:0)|(mark[rt][2]?2:0)|(mark[rt][4]?4:0));///表示该区间是由哪些颜色重叠而成的
    if(flag){
        me(sum[rt],0);///因为在跟新后，当前区间内的颜色要发生变化，所以需要重新赋值
        sum[rt][flag]=Hash[r+1]-Hash[l];
        for(int i=1;i<=7;i++){
            if(flag==(flag|i))///要是该种颜色或上当前颜色还是当前颜色，说明整个区间都不可能有该种颜色
                continue ;
            int temp=sum[rt<<1][i]+sum[rt<<1|1][i];///这里要减去区间里的其他颜色的长度
            sum[rt][flag]-=temp;
            sum[rt][flag|i]+=temp;
        }
    }else if(l==r){
        me(sum[rt],0);
    }else{
        for(int i=1;i<=7;i++)
            sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][i];
    }
}
void push_date(int L,int R,int x,int pos,int l,int r,int rt){
    if(L<=l&&R>=r){
        mark[rt][pos]+=x;
        push_up(l,r,rt);
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid)
        push_date(L,R,x,pos,lson);
    if(R>mid)
        push_date(L,R,x,pos,rson);
    push_up(l,r,rt);
}
int main()
{
    int t;
    int Case=1;
    scanf("%d",&t);
    int val[300];
    val['R']=1,val['G']=2,val['B']=4;
    while(t--){
        scanf("%d",&n);
        int len=0;
        for(int i=0;i<n;i++){
            char str[2];
            int x1,y1,x2,y2;
            scanf("%s%d%d%d%d",str,&x1,&y1,&x2,&y2);
            Hash[len]=x1;
            maps[len++]=node(x1,x2,y1,1,val[str[0]]);
            Hash[len]=x2;
            maps[len++]=node(x1,x2,y2,-1,val[str[0]]);
        }
        me(ans,0);
        sort(Hash,Hash+len);
        sort(maps,maps+len);
        int tlen=unique(Hash,Hash+len)-Hash;
        for(int i=0;i<len;i++){
            int l=lower_bound(Hash,Hash+tlen,maps[i].l)-Hash;
            int r=lower_bound(Hash,Hash+tlen,maps[i].r)-Hash-1;
            if(l<=r)
                push_date(l,r,maps[i].cnt,maps[i].pos,0,tlen-1,1);
            for(int j=1;j<=7;j++){
                ans[j]+=sum[1][j]*(ll)(maps[i+1].h-maps[i].h);
            }
        }
        printf("Case %d:\n",Case++);///下面这一行的输出颜色顺序，一定要注意我们用的二进制表示颜色
        printf("%lld\n%lld\n%lld\n%lld\n%lld\n%lld\n%lld\n",ans[1],ans[2],ans[4],ans[3],ans[5],ans[6],ans[7]);
    }
    return 0;
}