当前位置:首页 > 数据结构 > 线段树 > 正文
POJ2777CountColor
1186+

题目大意:一段包含为1到n的纸条,原来是颜色1,现在不断地往区间[x,y]涂色, 如何快速回答指定区间的不同颜色数量?

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

解题思路

往一个区间涂色,即区间赋值,用线段树可以解决。如何求区间颜色数量呢?如果线段记录的是颜色数量,父亲结点跟儿子结点的颜色数量关系就比较混乱了,因为如果左右两边颜色又重复,就不是直接相加的关系了。因此,线路不应该直接记录颜色的数量,而应该记录颜色的状态。题目说颜色数量不超过30,我们可以用一个int变量记录颜色状态,那么父亲结点的颜色状态就等于左右儿子颜色状态的或。查询到区间颜色状态后,可以用位运算统计状态中的颜色数量(二进制中1的个数)。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,

POJ2777CountColor:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter