180 人解决，287 人已尝试。
218 份提交通过，共有 1343 份提交。
3.8 EMB 奖励。
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:
- 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$ .
- 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
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
创建: 2 年，4 月前.
修改: 2 年，4 月前.
最后提交: 6 月，2 周前.
来源: N/A
题目标签