POJ 2777 Count Color【線分樹区間カバー】

Count Color
http://poj.org/problem?id=2777
Time Limit: 1000 MS
 
メモリLimit: 65536 K
Total Submissions: 54255
 
Acceepted: 16304
Description
Chosen Proble m Solving and Program design as,you are required to solive all kids of probles.Here,we get a new problem.  The e e is a very long board with length L centimeter、L is a positive integer、so we can evernly divide the board into L segments、and the y are labeled by 1、2、…L from left to Right、each is 1 centimewers.Nollaton.  1.「C A B C」Color the board from segment A to segment B withカラーカラー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 wods to describe a色(red、green、blue、yelloww...)、so you may asume that the total number of different colors T colorsT isssmake.Tomakeitsimple、we express thethethethethethethe aapapapapapapapapapapapapapapapapars the the thethethe thethethethe affs s s s s thethethethethethethethethethethersrsrs aaaaaffs s thethethethethethethethethethethethe aaafffs s s s thethethethethetheof 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.Follwing O lines,each contains"C"or"P B"(herstainger A,arefirs A,arever.)
Output
Ouut result 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

ソurce
POJ Monthly-20.03.26、dododo
題意
本のとても長い(L)の画板、T種の色があって、O個の操作;操作ごとに一つの区間を一つの色にしたり、一つの区間に含まれる色の数を調べたりします.
考え方
線分樹、区間カバー
C++コード

#include
#include

using namespace std;

#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

const int N=100100;
int color[N<<2];
bool vis[35];
int ans;

void pushup(int rt)
{
	if(color[rt<<1]==-1||color[rt<<1|1]==-1||color[rt<<1]!=color[rt<<1|1])
	  color[rt]=-1;
	else 
	  color[rt]=color[rt<<1];
}

void build(int l,int r,int rt)
{
	if(l==r)
	{
		color[rt]=1;
		return;
	}
	int m=(l+r)>>1;
	build(ls);
	build(rs);
	pushup(rt);
}

void pushdown(int rt)
{
	if(color[rt]>0)
	{
		color[rt<<1]=color[rt<<1|1]=color[rt];
	}
}

void update(int L,int R,int C,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		color[rt]=C;
		return;
	}
	int m=(l+r)>>1;
	pushdown(rt);
	if(L<=m)
	  update(L,R,C,ls);
	if(R>m)
	  update(L,R,C,rs);
	pushup(rt);
}


void query(int L,int R,int l,int r,int rt)
{
	if(color[rt]>0)
	{
		if(vis[color[rt]]==false) ans++;
		vis[color[rt]]=true;
		return;
	} 
	if(l==r) return;
	int m=(l+r)>>1;
	pushdown(rt);
	if(L<=m)
	  query(L,R,ls);
	if(R>m)
	  query(L,R,rs);
}

int main()
{
    int n,t,q;
    while(~scanf("%d%d%d",&n,&t,&q))
    {
    	build(1,n,1);
        while(q--)
        {
            char op;
            int L,R,C;
            scanf(" %c",&op);
            if(op=='C')
            { 
                scanf("%d%d%d",&L,&R,&C);
                update(L,R,C,1,n,1);
            }
            else
            {
                scanf("%d%d",&L,&R);
                memset(vis,0,sizeof(vis));
                ans=0;
                query(L,R,1,n,1);
                printf("%d
",ans);
            }
        }
    }
    return 0;
}