POJ2777--Count Color
Description
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
Output
Sample Input
2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2
Sample Output
2 1
题目描述：
首先对一个木板，长度为L，颜色种类为T，有O次询问，一开始建树，初始时将所有的树颜色设为1；
随后进行操作，如果改变颜色，改区间的颜色改变，包含此区间的颜色变为-1，因为这个区间不在是
纯色，这个区间有多种颜色。用一个颜色的数组储存所以颜色出现的次数，一开始都为0，查询时如果
查询的区间不为-1，表示该区间只有一种颜色，将这种颜色的数量+1，如果为-1.则继续搜索孩子。
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 100005
int colors[35],l,t,o,a,b,c,ans;
char ch;
struct node
{
int left;
int right;
int color;
}tree[maxn<<2];
void build(int l,int r,int k)
{
tree[k].left=l;
tree[k].right=r;
tree[k].color=1;
if(l==r)
return;
int mid=(l+r)/2;
build(l,mid,k<<1);
build(mid+1,r,k<<1|1);
}
void update(int l,int r,int c,int k)
{
if(tree[k].color==c)
return;
if(tree[k].left==l&&tree[k].right==r)
{
tree[k].color=c;
return;
}
if(tree[k].color!=-1)
{
tree[k<<1].color=tree[k<<1|1].color=tree[k].color;
tree[k].color=-1;
}
int mid=(tree[k].left+tree[k].right)/2;
if(mid>=r)
{
update(l,r,c,k<<1);
}
else if(mid<l)
{
update(l,r,c,k<<1|1);
}
else
{
update(l,mid,c,k<<1);
update(mid+1,r,c,k<<1|1);
}
}
void qurey(int l,int r,int k)
{
if(tree[k].color!=-1)
{
colors[tree[k].color]=1;
}
else
{
int mid=(tree[k].left+tree[k].right)/2;
if(mid>=r)
{
qurey(l,r,k<<1);
}
else if(mid<l)
{
qurey(l,r,k<<1|1);
}
else
{
qurey(l,mid,k<<1);
qurey(mid+1,r,k<<1|1);
}
}
}
int main()
{
while(scanf("%d%d%d",&l,&t,&o)!=EOF)
{
build(1,l,1);
while(o--)
{
getchar();
scanf("%c",&ch);
if(ch=='C')
{
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1);
}
if(ch=='P')
{
memset(colors,0,sizeof(colors));
scanf("%d%d",&a,&b);
ans=0;
qurey(a,b,1);
for(int i=1;i<=t;i++)
{
if(colors[i]!=0)
ans++;
}
printf("%d\n",ans);
}
}
}
return 0;
}