P17830 [CSP-J 2026] 纸牌游戏 / card（民间数据）

小 Z 正在玩一种单人纸牌游戏。 他有一叠特制的纸牌，共有 $n$ 张，从上到下的点数依次为 $a_1,a_2,\ldots,a_n$。每张牌的点数都是 $1$ 到 $m$ 之间的整数，且每种点数都出现至少一次。 小 Z 将进行 $n$ 局相互独立的游戏。每局开始前，他会将所有牌按原顺序放回牌堆，并清空桌面。在第 $i$（$1\le i\le n$）局中，他跳过前 $i-1$ 张牌，依次打出第 $i$ 张到第 $n$ 张牌，这些牌的点数依次为 $a_i,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 解释 对于第 $1$ 局游戏，小 Z 依次打出点数为 $1,2,1,3$ 的牌： 1. 打出第 $1$ 张牌（点数为 $1$）后，桌面上只有一张点数为 $1$ 的牌； 2. 打出第 $2$ 张牌（点数为 $2$）后，桌面上从左到右的牌的点数依次为 $1,2$； 3. 打出第 $3$ 张牌（点数为 $1$）后，先收走桌面上点数为 $1,2$ 的两张牌，再放上新打出的 $1$，桌面上只有一张点数为 $1$ 的牌； 4. 打出第 $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$ 局。 ### 样例 3 见题目目录下的 `card/3.in` 与 `card/3.ans`。 该样例满足测试点 $4\sim 6$ 的约束条件。 ### 样例 4 见题目目录下的 `card/4.in` 与 `card/4.ans`。 该样例满足测试点 $7\sim 9$ 的约束条件。 ### 样例 5 见题目目录下的 `card/5.in` 与 `card/5.ans`。 该样例满足测试点 $15\sim 17$ 的约束条件。 ### 样例 6 见题目目录下的 `card/6.in` 与 `card/6.ans`。 该样例满足测试点 $21,22$ 的约束条件。 ### 数据范围 对于所有测试数据，均有： - $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$）满足 $a_i\ne a_{i+1}$。