← 返回题目列表

AtCoder · abc464_c

C. 羽毛调色板

中文机器翻译题面 查看原题

分数: 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 总共有不同的颜色。