Problem #4551 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 512 MB

George is a painter.

Now there is a wall divided into $n$ parts from left to right. We use a sequence of integers $a_{1}, a_{2} \dots a_{n}$ to represent the color of each part. That is, $a_{i}$ represents the color of the $i$ -th wall.

At the beginning, $a_{i} = 0$ for all $1 \leq i \leq n$ , which means that the color of all $n$ parts is $0$ .

Next, George will give you $m$ operations. Each operation is in one of the following two types:

George paints the last $x$ parts of the wall with the color $y$ . That is, for all $n - x + 1 \leq i \leq n$ , modify $a_{i}$ into $y$ .
George asks you: how many different colors appear on the whole wall right now?

Can you answer his questions quickly and accurately?

输入格式

The first line contains two positive integers $n, m$ , indicating the number of parts of the wall and the number of operations, respectively.

The next $m$ lines, each is in one of the following two types:

Input three integers $1, x, y$ , indicating painting the last $x$ parts of the wall with color $y$ .
Input an integer, $2$ , indicating a question —— how many different colors appear on the whole wall right now?

输出格式

For each operation, output one line, which contains an integer, indicating the answer.

样例

Input

Output

1
2

Input

Output

2
2
3

提示

$1 \leq n, m \leq 5 \times 10^{5}$

$1 \leq x \leq n$

$0 \leq y \leq 10^{6}$

Sample 2 Explanation:

After the first painting, the color of the $5$ parts become:

00011

After the second painting of the wall, the color of the $5$ parts become:

02222

After the third painting of the wall, the color of the $5$ parts become:

02223

180 人解决，287 人已尝试。

218 份提交通过，共有 1343 份提交。

3.8 EMB 奖励。

创建: 3 年，4 月前.

修改: 3 年，4 月前.

最后提交: 1 年，6 月前.

来源: N/A

4551. Paint

输入格式

输出格式

样例

提示

服务

开源

关于我们