F - Count the Colors - zoj 1610（区间覆盖）

有一块很长的画布，现在想在这块画布上画一些颜色，不过后面画的颜色会把前面画的颜色覆盖掉，现在想知道画完后这块画布的颜色分布，比如 1号颜色有几块，2号颜色有几块。。。。

***********************************************************************

分析：基本上跟帖海报是一样的，不过最后要求输出的是这种颜色的画有几块，可以按照贴海报的方式先做出来，然后对每个点进行查询，不晓得复杂度会不会太高。不过还是先试一下吧。

注意：如果出现

Segmentation Fault

可以看看是不是树建的小了，不能拿N建树

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define Lson root<<1,L,tree[root].Mid()

#define Rson root<<1|1,tree[root].Mid()+1,R

const int maxn = ;

struct Hook{int l, r, c;}p[maxn];

struct Tree{

    int L, R;

    int color;//记录颜色

    int Mid(){return (L+R)/;}

}tree[maxn*];

int Color[maxn];

void CoverColor(int L, int R, int e)//把区间LR涂成颜色e

{

    for(int i=L; i<=R; i++)

        Color[i] = e;

}

void Build(int root, int L, int R)

{

    tree[root].L = L, tree[root].R = R;

    //0代表没有被颜色覆盖，1代表未覆盖，2代表子树有被别的颜色覆盖

    tree[root].color = ;

    if(L == R)return ;

    Build(Lson);

    Build(Rson);

}

void Up(int root)

{

    if(tree[root].L != tree[root].R)

    if(tree[root<<].color ==  && tree[root<<|].color == )

        tree[root].color = ;

}

void Insert(int root, int L, int R, int e)

{

    if(tree[root].color == )return ;

    if(tree[root].L == L && tree[root].R == R && !tree[root].color)

    {

        tree[root].color = ;

        CoverColor(L, R, e);

        return ;

    }

    tree[root].color = ;

    if(R <= tree[root].Mid())

        Insert(root<<, L, R, e);

    else if(L > tree[root].Mid())

        Insert(root<<|, L, R, e);

    else

    {

        Insert(Lson, e);

        Insert(Rson, e);

    }

    Up(root);

}

int main()

{

    int N;

    while(scanf("%d", &N) != EOF)

    {

        int i, ans[maxn] = {};

        for(i=; i<=N; i++)

            scanf("%d%d%d", &p[i].l, &p[i].r, &p[i].c);

        Build(, , maxn-);

        memset(Color, -, sizeof(Color));

        for(i=N; i>; i--)//因为给的是紧密区间，而建的树点的，所以把左边的+1，变成点覆盖的

            Insert(, p[i].l+, p[i].r, p[i].c);

        for(i=; i<maxn; i++)

        {

            if( Color[i]!=- && (!i || Color[i]!=Color[i-]) )

                ans[Color[i]]++;

        }

        for(i=; i<maxn; i++)if(ans[i])

            printf("%d %d\n", i, ans[i]);

        printf("\n");

    }

    return ; }

巴特西

F - Count the Colors - zoj 1610（区间覆盖）

最新文章

热门文章