4551. Paint

单点时限: 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\cdots 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\le i \le 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:

  1. George paints the last $x$ parts of the wall with the color $y$. That is, for all $n-x+1 \le i \le n$ , modify $a_i$ into $y$ .
  2. 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:

  1. Input three integers $1,x,y$, indicating painting the last $x$ parts of the wall with color $y$.

  2. 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
5 3
2
1 2 1
2
Output
1
2
Input
5 6
1 2 1
2
1 4 2
2
1 1 3
2
Output
2
2
3

提示

$1\le n,m \le 5\times 10^5$

$1\le x \le n$

$0\le y \le 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

176 人解决,283 人已尝试。

210 份提交通过,共有 1318 份提交。

3.9 EMB 奖励。

创建: 9 月,2 周前.

修改: 9 月,2 周前.

最后提交: 1 周,3 天前.

来源: N/A

题目标签