程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU-4419-Colourful Rectangle(線段樹)

HDU-4419-Colourful Rectangle(線段樹)

編輯：C++入門知識

HDU-4419-Colourful Rectangle(線段樹)

Problem Description 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

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

Source 2012 ACM/ICPC Asia Regional Hangzhou Online
思路：維護區間R,G,B三種顏色的數量，更新時判斷區間的組合顏色，再考慮與左右兒子的顏色組合的情況。

#include 
#include 
#include 
#include 
using namespace std;

mapii;

struct S{
int r,g,b;
int cr,cg,cb,crg,crb,cgb,crgb;
}node[200000];

struct L{
int pos,l,r,type,flag;

bool operator<(const L &p) const
{
    return pos>1;

        build(idx<<1,s,mid);
        build(idx<<1|1,mid+1,e);
    }
}

void pop(int idx,int s,int e)
{
    node[idx].cr=0;
    node[idx].cg=0;
    node[idx].cb=0;
    node[idx].crg=0;
    node[idx].crb=0;
    node[idx].cgb=0;
    node[idx].crgb=0;

    if(node[idx].r && node[idx].g && node[idx].b)
    {
        node[idx].crgb+=node[idx<<1].cr+node[idx<<1|1].cr;
        node[idx].crgb+=node[idx<<1].cg+node[idx<<1|1].cg;
        node[idx].crgb+=node[idx<<1].cb+node[idx<<1|1].cb;
        node[idx].crgb+=node[idx<<1].crg+node[idx<<1|1].crg;
        node[idx].crgb+=node[idx<<1].crb+node[idx<<1|1].crb;
        node[idx].crgb+=node[idx<<1].cgb+node[idx<<1|1].cgb;
        node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb;

        node[idx].crgb+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb;
    }

    if(!node[idx].r && node[idx].g && node[idx].b)
    {
        node[idx].crgb+=node[idx<<1].cr+node[idx<<1|1].cr;
        node[idx].cgb+=node[idx<<1].cg+node[idx<<1|1].cg;
        node[idx].cgb+=node[idx<<1].cb+node[idx<<1|1].cb;
        node[idx].crgb+=node[idx<<1].crg+node[idx<<1|1].crg;
        node[idx].crgb+=node[idx<<1].crb+node[idx<<1|1].crb;
        node[idx].cgb+=node[idx<<1].cgb+node[idx<<1|1].cgb;
        node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb;

        node[idx].cgb+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb;
    }

    if(node[idx].r && !node[idx].g && node[idx].b)
    {
        node[idx].crb+=node[idx<<1].cr+node[idx<<1|1].cr;
        node[idx].crgb+=node[idx<<1].cg+node[idx<<1|1].cg;
        node[idx].crb+=node[idx<<1].cb+node[idx<<1|1].cb;
        node[idx].crgb+=node[idx<<1].crg+node[idx<<1|1].crg;
        node[idx].crb+=node[idx<<1].crb+node[idx<<1|1].crb;
        node[idx].crgb+=node[idx<<1].cgb+node[idx<<1|1].cgb;
        node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb;

        node[idx].crb+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb;
    }

    if(node[idx].r && node[idx].g && !node[idx].b)
    {
        node[idx].crg+=node[idx<<1].cr+node[idx<<1|1].cr;
        node[idx].crg+=node[idx<<1].cg+node[idx<<1|1].cg;
        node[idx].crgb+=node[idx<<1].cb+node[idx<<1|1].cb;
        node[idx].crg+=node[idx<<1].crg+node[idx<<1|1].crg;
        node[idx].crgb+=node[idx<<1].crb+node[idx<<1|1].crb;
        node[idx].crgb+=node[idx<<1].cgb+node[idx<<1|1].cgb;
        node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb;

        node[idx].crg+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb;
    }

    if(node[idx].r && !node[idx].g && !node[idx].b)
    {
        node[idx].cr+=node[idx<<1].cr+node[idx<<1|1].cr;
        node[idx].crg+=node[idx<<1].cg+node[idx<<1|1].cg;
        node[idx].crb+=node[idx<<1].cb+node[idx<<1|1].cb;
        node[idx].crg+=node[idx<<1].crg+node[idx<<1|1].crg;
        node[idx].crb+=node[idx<<1].crb+node[idx<<1|1].crb;
        node[idx].crgb+=node[idx<<1].cgb+node[idx<<1|1].cgb;
        node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb;

        node[idx].cr+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb;
    }

    if(!node[idx].r && node[idx].g && !node[idx].b)
    {
        node[idx].crg+=node[idx<<1].cr+node[idx<<1|1].cr;
        node[idx].cg+=node[idx<<1].cg+node[idx<<1|1].cg;
        node[idx].cgb+=node[idx<<1].cb+node[idx<<1|1].cb;
        node[idx].crg+=node[idx<<1].crg+node[idx<<1|1].crg;
        node[idx].crgb+=node[idx<<1].crb+node[idx<<1|1].crb;
        node[idx].cgb+=node[idx<<1].cgb+node[idx<<1|1].cgb;
        node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb;

        node[idx].cg+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb;
    }

    if(!node[idx].r && !node[idx].g && node[idx].b)
    {
        node[idx].crb+=node[idx<<1].cr+node[idx<<1|1].cr;
        node[idx].cgb+=node[idx<<1].cg+node[idx<<1|1].cg;
        node[idx].cb+=node[idx<<1].cb+node[idx<<1|1].cb;
        node[idx].crgb+=node[idx<<1].crg+node[idx<<1|1].crg;
        node[idx].crb+=node[idx<<1].crb+node[idx<<1|1].crb;
        node[idx].cgb+=node[idx<<1].cgb+node[idx<<1|1].cgb;
        node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb;

        node[idx].cb+=vv[e]-vv[s-1]-node[idx].cr-node[idx].cg-node[idx].cb-node[idx].crg-node[idx].crb-node[idx].cgb-node[idx].crgb;
    }

    if(!node[idx].r && !node[idx].g && !node[idx].b)//別漏了這個
    {
        node[idx].cr+=node[idx<<1].cr+node[idx<<1|1].cr;
        node[idx].cg+=node[idx<<1].cg+node[idx<<1|1].cg;
        node[idx].cb+=node[idx<<1].cb+node[idx<<1|1].cb;
        node[idx].crg+=node[idx<<1].crg+node[idx<<1|1].crg;
        node[idx].crb+=node[idx<<1].crb+node[idx<<1|1].crb;
        node[idx].cgb+=node[idx<<1].cgb+node[idx<<1|1].cgb;
        node[idx].crgb+=node[idx<<1].crgb+node[idx<<1|1].crgb;
    }
}

void update(int idx,int s,int e,int l,int r,int val,int flag)
{
    if(l==s && r==e)
    {
        switch(val)
        {
            case 1:node[idx].r+=flag;break;
            case 2:node[idx].g+=flag;break;
            case 3:node[idx].b+=flag;break;
        }

        pop(idx,s,e);
    }
    else
    {
        int mid=(s+e)>>1;

        if(r<=mid) update(idx<<1,s,mid,l,r,val,flag);
        else if(l>mid) update(idx<<1|1,mid+1,e,l,r,val,flag);
        else
        {
            update(idx<<1,s,mid,l,mid,val,flag);
            update(idx<<1|1,mid+1,e,mid+1,r,val,flag);
        }

        pop(idx,s,e);
    }
}

int main()
{
    int T,n,i,cnt,x1,y1,x2,y2,num,last,cases=1;
    long long ar,ag,ab,arg,arb,agb,argb;
    char s[5];

    scanf("%d",&T);

    while(T--)
    {
        ii.clear();

        ar=ag=ab=arg=arb=agb=argb=0;

        scanf("%d",&n);

        cnt=0;

        num=0;

        while(n--)
        {
            scanf("%s%d%d%d%d",s,&x1,&y1,&x2,&y2);

            if(!ii[y1]) lisan[num++]=y1,ii[y1]=1;
            if(!ii[y2]) lisan[num++]=y2,ii[y2]=1;

            line[cnt].pos=x1;
            line[cnt].l=y1;
            line[cnt].r=y2;

            line[cnt+1].pos=x2;
            line[cnt+1].l=y1;
            line[cnt+1].r=y2;

            if(s[0]=='R')
            {
                line[cnt].flag=1;
                line[cnt++].type=1;
                line[cnt].flag=-1;
                line[cnt++].type=1;
            }
            else if(s[0]=='G')
            {
                line[cnt].flag=1;
                line[cnt++].type=2;
                line[cnt].flag=-1;
                line[cnt++].type=2;
            }
            else
            {
                line[cnt].flag=1;
                line[cnt++].type=3;
                line[cnt].flag=-1;
                line[cnt++].type=3;
            }
        }

        sort(line,line+cnt);
        sort(lisan,lisan+num);

        for(i=0;i