97322 - 纸牌游戏card（非官方数据）

题目描述

小 Z 正在玩一种单人纸牌游戏。

他有一叠特制的纸牌，共有 $n$ 张，从上到下的点数依次为 $a_1,a_2,\ldots,a_n$ 。每张牌的点数都是 $1$ 到 $m$ 之间的整数，且每种点数都出现至少一次。

小 Z 将进行 $n$ 局相互独立的游戏。每局开始前，他会将所有牌按原顺序放回牌堆，并清空桌面。在第 $i$ （ $1\le i\le n$ ）局中，他跳过前 $i-1$ 张牌，依次打出第 $i$ 张到第 $n$ 张牌，这些牌的点数依次为 $ai,a{i+1},\ldots,a_n$。

桌面上的牌始终从左到右排成一行。打出一张点数为 $k$ 的牌时：

若桌面上没有点数为 $k$ 的牌，就将这张牌放在最右端；
否则，收走桌面上点数为 $k$ 的牌及其右侧的所有牌，再把这张牌放在最右端。被收走的牌在本局中不再使用。

由上述规则可知，任意时刻桌面上同一种点数的牌至多只有一张。

最后一张牌打出后，本局游戏结束。

例如，若桌面上从左到右的牌的点数依次为 $1,4,2$ ，则打出一张点数为 $3$ 的牌后，桌面上从左到右的牌的点数依次为 $1,4,2,3$ 。接着打出一张点数为 $4$ 的牌时，桌面上原来点数为 $4$ 的牌及其右侧的所有牌（点数依次为 $4,2,3$ ）被收走，再把新打出的 $4$ 放在最右端，此时桌面上从左到右的牌的点数依次为 $1,4$ 。

你需要帮助小 Z 依次求出，对于每个 $i=1,2,\ldots,m$ ，在所有 $n$ 局游戏中，有多少局结束时桌面上留有点数为 $i$ 的牌。

输入

从文件 card.in 中读入数据。

输入的第一行包含两个正整数 $n,m$ ，分别表示牌的数量和点数种类数。

输入的第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ ，依次表示小 Z 的牌从上到下的点数。

输出

输出到文件 card.out 中。

输出一行 $m$ 个非负整数，其中第 $i$ （ $1\le i\le m$ ）个整数表示在所有 $n$ 局游戏中，有多少局结束时桌面上留有点数为 $i$ 的牌。

样例

样例 1

输入

4 3
1 2 1 3

输出

3 1 4

样例 2

输入

10 3
3 1 2 1 3 2 3 1 2 1

输出

10 3 3

提示

对于第 $1$ 局游戏，小 Z 依次打出点数为 $1,2,1,3$ 的牌：

打出第 $1$ 张牌（点数为 $1$ ）后，桌面上只有一张点数为 $1$ 的牌；
打出第 $2$ 张牌（点数为 $2$ ）后，桌面上从左到右的牌的点数依次为 $1,2$ ；
打出第 $3$ 张牌（点数为 $1$ ）后，先收走桌面上点数为 $1,2$ 的两张牌，再放上新打出的 $1$ ，桌面上只有一张点数为 $1$ 的牌；
打出第 $4$ 张牌（点数为 $3$ ）后，桌面上从左到右的牌的点数依次为 $1,3$ 。

因此第 $1$ 局游戏结束时，桌面上从左到右的牌的点数依次为 $1,3$ 。

对于第 $2$ 局游戏，小 Z 依次打出点数为 $2,1,3$ 的牌，结束时桌面上从左到右的牌的点数依次为 $2,1,3$ 。

对于第 $3$ 局游戏，小 Z 依次打出点数为 $1,3$ 的牌，结束时桌面上从左到右的牌的点数依次为 $1,3$ 。

对于第 $4$ 局游戏，小 Z 仅打出一张点数为 $3$ 的牌，结束时桌面上只有一张点数为 $3$ 的牌。

因此，在全部 $4$ 局游戏中：

有 $3$ 局游戏结束时，桌面上留有点数为 $1$ 的牌，即第 $1,2,3$ 局；
有 $1$ 局游戏结束时，桌面上留有点数为 $2$ 的牌，即第 $2$ 局；
有 $4$ 局游戏结束时，桌面上留有点数为 $3$ 的牌，即全部 $4$ 局。

数据范围

对于所有测试数据，均有：

$2\le n\le 5\times 10^5$ ， $1\le m\le 3\times 10^5$ ；
对于所有 $i$ （ $1\le i\le n$ ），均有 $1\le a_i\le m$ ；
每种点数都出现至少一次，即对于所有 $i$ （ $1\le i\le m$ ），均存在 $j$ （ $1\le j\le n$ ）满足 $a_j=i$ 。

::cute-table{tuack}

测试点编号	$n\le$	$m\le$	特殊性质
$1\sim 3$	$5$	$2$	无
$4\sim 6$	$500$	$200$	无
$7\sim 9$	$5000$	$3000$	A
$10\sim 12$	$5000$	$3000$	无
$13,14$	$2\times 10^5$	$2$	无
$15\sim 17$	$2\times 10^5$	$3000$	B
$18,19$	$2\times 10^5$	$3000$	无
$20$	$2\times 10^5$	$10^5$	A
$21,22$	$2\times 10^5$	$10^5$	无
$23\sim 25$	$5\times 10^5$	$3\times 10^5$	无

特殊性质 A： $a_1\le a_2\le\cdots\le a_n$ 。

特殊性质 B：至多存在 $4999$ 个 $i$ （ $1\le i\le n-1$ ）满足 $ai\ne a{i+1}$。

来源

CSP-J 2026