分数: 300 点
问题陈述
高桥观察到 N 鸟,编号 1, 2, \dots, N,结束 M 天。
高桥观察到的每只鸟都具有以下特征之一: N 颜色,编号 1, 2, \dots, N,而这些鸟有一个有趣的特点:它们的颜色在观察期间会发生变化。
鸟 i 有颜色 A_i 在当天或之前的观察中 D_i - 1和颜色 B_i 在当天或之后的观察中 D_i.
这里,如果 D_i = 1,那么鸟的颜色是 B_i 从当天的观察来看 1,如果 A_i = B_i,那么在观察期间鸟的颜色没有变化。
对于每个 j = 1, 2, \dots, M, 找出当天不同颜色的鸟的数量 j.
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 D_1 B_1 A_2 D_2 B_2 \vdots A_N D_N B_N
输出
输出 M 行。
的 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
在此输入中,7 天内观察到了 6 只鸟。
- 当天 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 总共有不同的颜色。