HUD-4419 Colourful Rectangle 線段樹+掃描線+離散

   題意：分別用R,G,B三種顏色覆蓋一平面區域，不同的顏色重合會產生不同的顏色：RG，RB，BG，RGB，求最後每種顏色的面積。
        矩形面積並，掃描線的加強版。線段樹記錄分別7重顏色的的長度，然後記錄每種顏色覆蓋的次數。
  My code：
[cpp] 
//STATUS:C++_AC_250MS_5260KB   
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<algorithm> 
#include<string> 
#include<vector> 
#include<queue> 
#include<stack> 
#include<math.h> 
#include<map> 
#include<set> 
using namespace std; 
#define LL __int64 
#define pii pair<int,int> 
#define mem(a,b) memset(a,b,sizeof(a)) 
#define lrt rt<<1 
#define rrt rt<<1|1 
#define lson l,mid,rt<<1 
#define rson mid+1,r,rt<<1|1 
#define Max(x,y) ((x)>(y)?(x):(y)) 
#define Min(x,y) ((x)<(y)?(x):(y)) 
const int MAX=10010,INF=200000000; 
const double esp=1e-6; 
 
struct Tree{ 
    int len[8],cou[5]; 
}ret[MAX<<3]; 
struct Node{ 
    int x,y1,y2,lorr,val; 
}nod[MAX<<1]; 
 
int cmp1(const void *a,const void *b){ 
    return ((Node*)a)->x - ((Node*)b)->x; 
} 
int cmp2(const void *a,const void *b){ 
    return *(int*)a - *(int*)b; 
} 
 
void update(int l,int r,int rt); 
void pushup(int rt,int l,int r); 
LL ans[8]; 
int y[MAX<<1]; 
int T,n,k,a,b,cc,x1,x2,jorj; 
map<int,int> q; 
int main() 
{ 
//  freopen("in.txt","r",stdin); 
    int i,j,ca=1; 
    char str[2]; 
     
    scanf("%d",&T); 
    while(T--) 
    { 
        k=0; 
        q.clear(); 
        mem(ans,0); 
        mem(ret,0); 
        scanf("%d",&n); 
         
        n<<=1; 
        for(i=0;i<n;i+=2){ 
            scanf("%s%d%d%d%d",str,&nod[i].x,&nod[i].y1, 
                &nod[i+1].x,&nod[i+1].y2); 
            nod[i].lorr=1; 
            nod[i+1].lorr=0; 
            nod[i+1].val=nod[i].val=(str[0]=='R'?1:(str[0]=='G'?2:4)); 
            nod[i].y2=nod[i+1].y2; 
            nod[i+1].y1=nod[i].y1; 
            if(!q[ nod[i].y1 ]){ 
                q[ nod[i].y1 ]=1; 
                y[k++]=nod[i].y1; 
            } 
            if(!q[ nod[i].y2 ]){ 
                q[ nod[i].y2 ]=1; 
                y[k++]=nod[i].y2; 
            } 
        } 
     
        qsort(nod,n,sizeof(Node),cmp1); 
        qsort(y,k,sizeof(int),cmp2); 
        q.clear(); 
        for(i=0;i<k;i++) 
            q[ y[i] ]=i; 
 
        for(i=0;i<n;i++){ 
            jorj=nod[i].lorr; 
            a=q[nod[i].y1]; 
            b=q[nod[i].y2]-1; 
            cc=nod[i].val; 
            update(0,k-1,1); 
            if(nod[i].x!=nod[i+1].x){ 
                for(j=1;j<8;j++) 
                    ans[j]+=(LL)(nod[i+1].x-nod[i].x)*(LL)ret[1].len[j]; 
            } 
        } 
 
        printf("Case %d:\n",ca++); 
        printf("%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n", 
            ans[1],ans[2],ans[4],ans[3],ans[5],ans[6],ans[7]); 
    } 
    return 0; 
} 
 
void pushup(int rt,int l,int r) 
{ 
    int i,sta=((ret[rt].cou[1]?1:0) | (ret[rt].cou[2]?2:0) | (ret[rt].cou[4]?4:0)); 
    if(sta){ 
        mem(ret[rt].len,0); 
        ret[rt].len[sta]=y[r+1]-y[l]; 
        for(i=1;i<8;i++){ 
            if(sta!=(sta|i)){ 
                int t=ret[lrt].len[i]+ret[rrt].len[i]; 
                ret[rt].len[sta|i]+=t; 
                ret[rt].len[sta]-=t; 
            } 
        } 
    } 
    else if(l!=r){ 
        for(i=1;i<8;i++) 
            ret[rt].len[i]=ret[lrt].len[i]+ret[rrt].len[i]; 
    } 
    else mem(ret[rt].len,0); 
} 
 
void update(int l,int r,int rt) 
{ 
    if(a<=l && r<=b){ 
        jorj?ret[rt].cou[cc]++:ret[rt].cou[cc]--; 
        pushup(rt,l,r); 
        return; 
    } 
    int mid=(l+r)>>1; 
    if(a<=mid)update(lson); 
    if(b>mid)update(rson); 
    pushup(rt,l,r); 
}