首页 > 代码库 > HDU-4419-Colourful Rectangle(线段树)

HDU-4419-Colourful Rectangle(线段树)

2024-07-24 07:11:03   218人阅读

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

Source
2012 ACM/ICPC Asia Regional Hangzhou Online
 

思路：维护区间R,G,B三种颜色的数量，更新时判断区间的组合颜色，再考虑与左右儿子的颜色组合的情况。

#include <cstdio>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;

map<int,int>ii;

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<p.pos;
}

}line[20005];

int lisan[20005],vv[20005];

void build(int idx,int s,int e)
{
    node[idx].r=node[idx].g=node[idx].b=0;

    node[idx].cr=node[idx].cg=node[idx].cb=node[idx].crg=node[idx].crb=node[idx].cgb=node[idx].crgb=0;

    if(s!=e)
    {
        int mid=(s+e)>>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<num;i++)
        {
            ii[lisan[i]]=i+1;
            vv[i]=lisan[i];
        }

        build(1,1,num);

        for(i=0;i<cnt;i++)
        {
            if(i)
            {
                ar+=(long long)(line[i].pos-last)*(node[1].cr);
                ag+=(long long)(line[i].pos-last)*(node[1].cg);
                ab+=(long long)(line[i].pos-last)*(node[1].cb);
                arg+=(long long)(line[i].pos-last)*(node[1].crg);
                arb+=(long long)(line[i].pos-last)*(node[1].crb);
                agb+=(long long)(line[i].pos-last)*(node[1].cgb);
                argb+=(long long)(line[i].pos-last)*(node[1].crgb);
            }

            update(1,1,num,ii[line[i].l],ii[line[i].r]-1,line[i].type,line[i].flag);

            last=line[i].pos;
        }

        printf("Case %d:\n",cases++);

        printf("%I64d\n",ar);
        printf("%I64d\n",ag);
        printf("%I64d\n",ab);
        printf("%I64d\n",arg);
        printf("%I64d\n",arb);
        printf("%I64d\n",agb);
        printf("%I64d\n",argb);
    }
}

HDU-4419-Colourful Rectangle(线段树)


联系
我们