poj 2777 Count Color(線段樹) -开发者知识库

poj 2777 Count Color(線段樹) -开发者知识库,第1张

和poj 2528差不多

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m 1,r,rt<<1|1

const int MAXN = 100010;
//col[rt]=-1 表示rt節點管理的區間內的顏色是不同的顏色
//col[rt] != -1 表示當前區間都是同一種顏色
int col[MAXN<<2];
//查詢的時候用於標記顏色
int mark[33];
int res;

void build(int l, int r, int rt)
{
    col[rt] = 1;
    if(l == r) return;
    int m = (l r) >> 1;
    build(lson);
    build(rson);
}

void pushDown(int l, int r, int rt)
{
    if(col[rt] != -1)
    {
        col[rt<<1] = col[rt<<1|1] = col[rt];
        col[rt] = -1;
    }
}

void update(int L, int R, int c, int l, int r, int rt)
{
    if(l >= L && r <= R)
    {
        col[rt] = c;
        return ;
    }
    //假設當前區間都是同一種顏色,(L,R)和當前區間有交集,則要把當前區間
    //之前標記的顏色都推到子節點,然后再遞歸去更新需要更新的區間
    pushDown(l,r,rt);
    int m = (l r) >> 1;
    if(L <= m)
        update(L,R,c,lson);
    if(R > m)
        update(L,R,c,rson);
}

void query(int L, int R, int l, int r ,int rt)
{
    if(col[rt] != -1)
    {
        if(mark[col[rt]] == 0)
        {
            mark[col[rt]] = 1;
            res  ;
        }
        return;
    }
    if(l == r) return;
    int m = (l r) >> 1;
    if(L <= m) query(L,R,lson);
    if(R > m) query(L,R,rson);
}

int main()
{
    int L,T,O;
    char ch;
    int a,b,c;
    while(scanf("%d %d %d",&L,&T,&O) != EOF)
    {
        build(1,L,1);
        while(O--)
        {
            scanf(" %c",&ch);
            if(ch == 'C')
            {
                scanf("%d %d %d",&a,&b,&c);
                update(a,b,c,1,L,1);
            }
            else
            {
                scanf("%d %d",&a,&b);
                res = 0;
                memset(mark,0,sizeof(mark));
                query(a,b,1,L,1);
                printf("%d\n",res);
            }
        }
    }
    return 0;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复