A7695. Plumage Palette
编程题
入门
知识点
题目描述
高桥在 $M$ 天内观察了 $N$ 只鸟，编号为 $1, 2, \dots, N$。
每只被高桥观察到的鸟有 $N$ 种颜色之一（编号为 $1, 2, \dots, N$），且这些鸟具有一种有趣的特性：其颜色在观察期间可能发生变化。
对于鸟 $i$，在第 $D_i - 1$ 天及之前的所有观测中，其颜色为 $A_i$；而在第 $D_i$ 天及之后的所有观测中，其颜色为 $B_i$。
此处，若 $D_i = 1$，则该鸟自第 $1$ 天起颜色即为 $B_i$；若 $A_i = B_i$，则该鸟在整个观察期间颜色未发生变化。
对每个 $j = 1, 2, \dots, M$，求第 $j$ 天所观察到的鸟的不同颜色种数。
每只被高桥观察到的鸟有 $N$ 种颜色之一（编号为 $1, 2, \dots, N$），且这些鸟具有一种有趣的特性：其颜色在观察期间可能发生变化。
对于鸟 $i$，在第 $D_i - 1$ 天及之前的所有观测中，其颜色为 $A_i$；而在第 $D_i$ 天及之后的所有观测中，其颜色为 $B_i$。
此处，若 $D_i = 1$，则该鸟自第 $1$ 天起颜色即为 $B_i$；若 $A_i = B_i$，则该鸟在整个观察期间颜色未发生变化。
对每个 $j = 1, 2, \dots, M$，求第 $j$ 天所观察到的鸟的不同颜色种数。
输入格式
输入从标准输入中按以下格式给出：
> $N$ $M$
> $A_1$ $D_1$ $B_1$
> $A_2$ $D_2$ $B_2$
> $\vdots$
> $A_N$ $D_N$ $B_N$
> $N$ $M$
> $A_1$ $D_1$ $B_1$
> $A_2$ $D_2$ $B_2$
> $\vdots$
> $A_N$ $D_N$ $B_N$
输出格式
输出 $M$ 行。
第 $j$ 行应包含第 $j$ 天不同颜色的鸟的数量。
第 $j$ 行应包含第 $j$ 天不同颜色的鸟的数量。
输入输出样例
输入 #1
6 7 1 3 2 2 6 5 5 5 1 3 3 5 4 1 6 6 3 6
输出 #1
5 5 3 3 4 4 4
说明/提示
**样例 1 解释：**
本输入中，在七天内观测了六只鸟。
* 第 $1$ 天，每只鸟的颜色为 $1, 2, 5, 3, 6, 6$。共有 $5$ 种不同的颜色。
* 第 $2$ 天，每只鸟的颜色为 $1, 2, 5, 3, 6, 6$。共有 $5$ 种不同的颜色。
* 第 $3$ 天，每只鸟的颜色为 $2, 2, 5, 5, 6, 6$。共有 $3$ 种不同的颜色。
* 第 $4$ 天，每只鸟的颜色为 $2, 2, 5, 5, 6, 6$。共有 $3$ 种不同的颜色。
* 第 $5$ 天，每只鸟的颜色为 $2, 2, 1, 5, 6, 6$。共有 $4$ 种不同的颜色。
* 第 $6$ 天，每只鸟的颜色为 $2, 5, 1, 5, 6, 6$。共有 $4$ 种不同的颜色。
* 第 $7$ 天，每只鸟的颜色为 $2, 5, 1, 5, 6, 6$。共有 $4$ 种不同的颜色。
### 约束条件
* $1 \le N \le 3 \times 10^5$
* $1 \le M \le 3 \times 10^5$
* $1 \le A_i, B_i \le N$
* $1 \le D_i \le M$
* 所有输入值均为整数。
本输入中，在七天内观测了六只鸟。
* 第 $1$ 天，每只鸟的颜色为 $1, 2, 5, 3, 6, 6$。共有 $5$ 种不同的颜色。
* 第 $2$ 天，每只鸟的颜色为 $1, 2, 5, 3, 6, 6$。共有 $5$ 种不同的颜色。
* 第 $3$ 天，每只鸟的颜色为 $2, 2, 5, 5, 6, 6$。共有 $3$ 种不同的颜色。
* 第 $4$ 天，每只鸟的颜色为 $2, 2, 5, 5, 6, 6$。共有 $3$ 种不同的颜色。
* 第 $5$ 天，每只鸟的颜色为 $2, 2, 1, 5, 6, 6$。共有 $4$ 种不同的颜色。
* 第 $6$ 天，每只鸟的颜色为 $2, 5, 1, 5, 6, 6$。共有 $4$ 种不同的颜色。
* 第 $7$ 天，每只鸟的颜色为 $2, 5, 1, 5, 6, 6$。共有 $4$ 种不同的颜色。
### 约束条件
* $1 \le N \le 3 \times 10^5$
* $1 \le M \le 3 \times 10^5$
* $1 \le A_i, B_i \le N$
* $1 \le D_i \le M$
* 所有输入值均为整数。