← 返回题目列表

AtCoder · past18_d

D. 大乱斗

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

问题陈述

N 玩家编号 1 通过 N 正在玩多人格斗游戏。 当比赛开始时, N 玩家 输入 立刻响起。 最初,每个玩家的 比赛期间发生 分数 本实验的 is 0.

然后, M 事件。 每个事件都有类型 1 或输入 2 描述如下:

  • 类型 1:以以下格式表示。 玩家 x 攻击 玩家 y.
1 x y
  • 类型 2:以以下格式表示。 玩家 z 退出 的戒指。
2 z

当玩家退出擂台时,会立即发生以下事件:

  • 退出玩家的分数减少 1.
  • 如果退出的玩家自上次进入以来至少受到过一次攻击,则最后一次进行此类攻击的玩家的分数增加 1.
  • 然后,玩家再次进入擂台。

打印每个玩家的最终得分。

约束

  • 所有输入值均为整数。
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq x, y, z \leq N
  • x \neq y

输入

输入由标准输入按以下格式给出:

N M
\mathrm{event}_1
\mathrm{event}_2
\vdots
\mathrm{event}_M

对于 i = 1, 2, \ldots, M, \mathrm{event}_i 代表 i第一个事件, 并且是类型-1 或类型-2 问题陈述中描述的格式。

输出

对于 i = 1, 2, \ldots, N,打印最终得分 S_i 玩家的 i 采用以下格式,以空格分隔:

S_1 S_2 \ldots S_N

示例输入 1

4 6
1 2 3
1 4 3
2 3
1 2 1
2 2
2 3

示例输出 1

0 -1 -2 1

比赛开始时, 4 选手进入擂台,选手得分为 (S_1, S_2, S_3, S_4) = (0, 0, 0, 0)。 然后,在比赛期间发生以下事件:

  • 在 1-st 事件,玩家 2 攻击玩家 3.
  • 在 2-nd 事件,玩家 4 攻击玩家 3.
  • 在 3-rd 事件,玩家 3 退出,因此他们的分数减少了 1。 由于玩家 3的最后一个入口(即自比赛开始后),他们在 1-st 和 2-nd 事件。其中最后一张是玩家制作的 4,因此他们的分数增加了 1。 随后,玩家 3 再次进入铃声。
  • 在 4第一个事件,玩家 2 攻击玩家 1.
  • 在 5第一个事件,玩家 2 退出,因此他们的分数减少了 1。 由于玩家 2的最后一个入口(即自比赛开始以来),他们从未受到攻击。随后,玩家 2 再次进入铃声。
  • 在 6第一个事件,玩家 3 退出,因此他们的分数减少了 1。 由于玩家 3的最后一个入口(即自 3-rd 事件),他们从未受到攻击。 随后,玩家 3 再次进入铃声。

选手们的最终成绩为 (S_1, S_2, S_3, S_4) = (0, -1, -2, 1).


示例输入 2

5 20
1 2 5
1 4 5
2 2
1 4 1
1 3 1
1 3 2
1 5 4
1 4 5
1 3 1
1 1 2
1 4 5
1 3 2
1 5 2
1 3 2
1 5 4
2 1
1 4 5
1 5 1
2 3
2 3

示例输出 2

-1 -1 -1 0 0