「MCOI-05」追杀

ID: 6545

远端评测题

1000ms

128MiB

难度: 5

上传者:

标签>

O2优化

洛谷月赛

题目描述

Dream SMP 具有 $m$ 位玩家，编号为 $1$ 至 $m$ 。初始时，每一位玩家生命数量为 $3$ 。一位玩家 公认活着（canonically alive）当且仅当生命值非零。

Dream SMP 经常发生大型战争，于是会有玩家杀（PvP）别的玩家。对于活着玩家 $u$ 与 $v$ ，如果 $u$ 杀 $v$ ， $v$ 的生命数量扣除一次。注意，如果 $u$ 或 $v$ 不为公认活着，杀没有影响。

总共按时序记录了 $n$ 次追杀 $1,2,\dots,n$ ，其中第 $k$ 次追杀为 $u_k$ 杀 $v_k$ 。

DreamXD（玩家 $0$ ）解锁了时空穿越超能力。他现在可以选取任何 $i,v$ 使得 $1\le i\le n+1$ 并且 $1\le v\le m$ ，穿越到第 $i-1$ 次追杀之后与第 $i$ 次追杀之前，并追杀玩家 $v$ 。 $i=n+1$ 表示穿越到第 $n$ 次追杀后。

不同 $i$ 和 $v$ 可能导致最终活着玩家集合不同。对于每一个 $x$ 使得 $0\le x\le m$ ，DreamXD 想知道，有多少种 $i,v$ 使最后公认活着玩家集合恰好含有 $x$ 位玩家？

第一行两个正整数 $n,m$ 。
接下来 $n$ 行，第 $k$ 行两个正整数 $u_k,v_k$ ，表示在第 $k$ 时刻， $u_k$ 追杀 $v_k$ 。

输出一行 $m+1$ 个正整数，其中第 $x$ 个为最终有 $x-1$ 位玩家活（不包含 Dream）的方案数。

2 2
1 2
1 2

0 3 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 72 456 0 0

本样例对应 Dream SMP 当前（4/26/2021) 情况，仅包含公认死亡，即对应剧本，的次数：

本题采用捆绑测试。

对于 $100\%$ 的数据， $1\le n\le6\times10^4$ ， $1\le m\le10^3$ ， $1\le u_i,v_i\le m$ 。