题意#

有 $m$ 位玩家 $1\sim m$，初始血量均为 $3$。玩家活着当且仅当生命值大于 $0$.

有 $n$ 次按时间顺序给定的追杀操作，每次形如 $(u_k,v_k)$，追杀操作按顺序进行。

执行操作 $u$ 追杀 $v$ 时，若二者都活着，那么 $v$ 的生命值减 $1$；否则不执行该操作。

现在有一名特殊玩家 $0$ 号，可以选取任意 $(i,v)$，其中 $1\leq i\leq n+1$，$1\leq v\leq m$，表示时空穿越到第 $i$ 次追杀前，并追杀玩家 $v$。

显然 $(i,v)$ 共有 $(n+1)\times m$ 个不同的选择方法，且不同的 $(i,v)$ 会导致最终存活玩家的集合不同。

对每个 $0\leq x\leq m$，求有多少种 $(i,v)$ 的选取方法，使最终恰有 $x$ 位玩家存活，输出 $m+1$ 个数。

$1\leq n\le 6\times 10^4$，$1\leq m\leq 10^3$，$1\leq u_i,v_i\leq m$.

对于 $16\%$ 的数据，$n,m\leq 100$.

对于另外 $41\%$ 的数据，$n\leq 10^3$.

对于 $100\%$ 的数据，$1\leq n\leq 6\times 10^4$，$1\leq m\leq 10^3$，$1\leq u_i,v_i\leq m$.

可以接受 $\mathcal{O}(nm)$ 的复杂度。

题解#

暴力？$\mathcal{O}(n^2m)$.

设 $f_{i,j}$ 表示：若在 $i$ 前穿越，追杀 $j$，最后存活的玩家数量。

对于追杀操作 $(u,v)$，无论在它前面还是后面，插入一个操作 $(0,x≠u)$，对结果的影响都是相同的。

因此，只有当 $j=u_i$ 时，$f_{i+1,j}≠f_{i,j}$，其他情况下都有 $f_{i,j}=f_{i+1,j}$.

所以我们尝试在每个操作 $(u,v)$ 前插入追杀 $u$ 的操作，插入后 $\mathcal{O}(n)$ 模拟一遍进程，更新 $f_{i,u_i}$.

这样的复杂度是 $\mathcal{O}(n^2)$ 的。

注意到，若第 $i$ 次追杀操作没有生效，也有 $f_{i,j}=f_{i+1,j}$，因此只需对所有生效的操作重新跑一遍。

最多有 $3⁢m$ 次生效操作，复杂度变为 $\mathcal{O}⁡(n⁢m)$，可以通过。