POJ-2777 Count Color（线段树，区间染色问题）

Count Color

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 40510 Accepted: 12215

Description

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.

There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, … L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:

1. “C A B C” Color the board from segment A to segment B with color C.
2. “P A B” Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, … color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains “C A B C” or “P A B” (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Output

Ouput results of the output operation in order, each line contains a number.

Sample Input

2 2 4

C 1 1 2

P 1 2

C 2 2 2

P 1 2

Sample Output

2

1

线段树区间染色问题，用一个tag数组标记一下就好了

#include <iostream>

#include <string.h>

#include <math.h>

#include <algorithm>

#include <stdlib.h>

using namespace std;

#define MAX 100000

int cover[MAX*4+5];

int n;

int t;

int m;

char a;

int x,y,z;

int tag[31];

void PushDown(int node)

{

    if(cover[node]!=-1)

    {

        cover[node<<1|1]=cover[node];

        cover[node<<1]=cover[node];

        cover[node]=-1;

    }

}

void Update(int node,int begin,int end,int left,int right,int num)

{

    if(left<=begin&&end<=right)

    {

        cover[node]=num;

        return;

    }

    PushDown(node);

    int m=(begin+end)>>1;

    if(left<=m)

        Update(node<<1,begin,m,left,right,num);

    if(right>m)

        Update(node<<1|1,m+1,end,left,right,num);

}

void Query(int node,int begin,int end,int left,int right,int &ans)

{

    if(cover[node]!=-1)

    {

        if(!tag[cover[node]])

        {

             ans++;

             tag[cover[node]]=1;

        }

        return;

    }

    PushDown(node);

    if(begin==end)

        return;

    int m=(begin+end)>>1;

    if(left<=m)

       Query(node<<1,begin,m,left,right,ans);

    if(right>m)

        Query(node<<1|1,m+1,end,left,right,ans);

}

int main()

{

    while(scanf("%d%d%d",&n,&t,&m)!=EOF)

    {

        memset(cover,0,sizeof(cover));

    for(int i=1;i<=m;i++)

    {

        getchar();

        scanf("%c",&a);

        if(a=='C')

        {

            scanf("%d%d%d",&x,&y,&z);

            Update(1,1,n,x,y,z-1);

        }

        else

        {

            memset(tag,0,sizeof(tag));

            scanf("%d%d",&x,&y);

            int ans=0;

            Query(1,1,n,x,y,ans);

            printf("%d\n",ans);

        }

    }

    }

    return 0;

}