hdu5023 （ 廣州網絡賽 ） 線段樹

hdu5023 （ 廣州網絡賽 ） 線段樹

題意是給你n個連續的點（1-n） m次操作 開始每個點都為2

兩種操作

1：把一段區間的點變為c

2：詢問區間有多少種點

很明顯的線段樹 對每個節點

flash表示該節點是否全為一樣的數 若是 則flash=這個數否則 flash=-1；

數組color記錄該節點輸得狀態 1表示有0表示沒有（我開成字符型 之前為int超類存了 真是無語）

然後 有更新和查詢操作

#include
#include
#include
using namespace std;

#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)

struct node
{
    char color[31];
    int flash;
}num[3* 1000000];
int leap[31];
int change(int mark,int k)
{
    for(int i=1;i<=30;i++)
    {
        num[mark].color[i]='0';
    }
    num[mark].color[k]='1';
    return 0;
}
int deal(int L,int R,int mark)
{
    num[mark].flash=2;
    change(mark,2);
    int mid=(L+R)/2;
    if(L==R) return 0;
    deal(L,mid,LL(mark));
    deal(mid+1,R,RR(mark));
    return 0;    
}//注意題目說開始時每個點都是2
int update(int L,int R,int left,int right,int mark,int k)
{
    int mid=(L+R)/2;
    if(num[mark].flash==k) return 0;//一個小優化
    if(L==left&&R==right)
    {
        num[mark].flash=k;
        change(mark,k);
        return 0;
    }
    if(num[mark].flash>0)
    {
        num[LL(mark)].flash=num[RR(mark)].flash=num[mark].flash;
        change(LL(mark),num[mark].flash);
        change(RR(mark),num[mark].flash);
    }
    if(right<=mid)
    {
        update(L,mid,left,right,LL(mark),k);
    }    
    else if(left>mid)
    {
        update(mid+1,R,left,right,RR(mark),k);
    }
    else
    {
        update(L,mid,left,mid,LL(mark),k);
        update(mid+1,R,mid+1,right,RR(mark),k);
    }
    for(int i=1;i<=30;i++)
    {
        if(num[LL(mark)].color[i]=='1'||num[RR(mark)].color[i]=='1')
        {
            num[mark].color[i]='1';
        }    
        else num[mark].color[i]='0';
    }
    if(num[LL(mark)].flash==num[RR(mark)].flash&&num[LL(mark)].flash>0) num[mark].flash=num[LL(mark)].flash;
    else num[mark].flash=-1;
    return 0;
}
int find(int L,int R,int left,int right,int mark)
{
    int mid=(L+R)/2;
    if(num[mark].flash!=-1)
    {
        leap[num[mark].flash]=1;
        return 0;
    }
    if(L==left&&R==right)
    {
        for(int i=1;i<=30;i++)
        {
            if(num[mark].color[i]=='1') leap[i]=1;
        }
    }
    if(right<=mid)
    {
        find(L,mid,left,right,LL(mark));
    }
    else if(left>mid)
    {
        find(mid+1,R,left,right,RR(mark));
    }
    else 
    {
        find(L,mid,left,mid,LL(mark));
        find(mid+1,R,mid+1,right,RR(mark));
    }
    return 0;
}
int main()
{
    int n,m,i,j,a,b,c;
    char str[5];
    while(~scanf("%d%d",&n,&m),n+m)
    {
        deal(1,n,1);
        for(j=1;j<=m;j++)
        {
            scanf("%s",str);
            if(str[0]=='P')
            {
                scanf("%d%d%d",&a,&b,&c);
                update(1,n,a,b,1,c);
            }
            else
            {
                scanf("%d%d",&a,&b);
                memset(leap,0,sizeof(leap));
                find(1,n,a,b,1);
                int d=1;
                for(i=1;i<=30;i++)
                {
                    if(leap[i])
                    {
                        if(d!=1) printf(" ");
                        printf("%d",i);
                        d++;
                    }
                }
                printf("\n");
            }
        }
    }
    return 0;
}