D. 纸牌游戏

    传统题 文件IO:card 1000ms 1024MiB

纸牌游戏

本题需要文件读写

文件 IO 为:输入文件 card.in,输出文件 card.out。请使用上述文件名读入和输出。

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

小 Z 有一叠共 nn 张的特制纸牌,从上到下的点数依次为 a1,a2,…,ana_1,a_2,\ldots,a_n。每张牌的点数为 11 到 mm 之间的整数,每种点数都至少出现一次。

小 Z 将进行 nn 局相互独立的游戏。每局开始前,所有牌都会按原顺序放回牌堆,桌面会被清空。在第 ii 局中,他跳过前 i−1i-1 张牌,依次打出第 ii 张到第 nn 张牌。

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

  • 如果桌面上没有点数为 kk 的牌,将新牌放在最右端;
  • 否则,收走桌面上点数为 kk 的牌及其右侧的所有牌,再将新牌放在最右端。被收走的牌在本局中不再使用。

因此,任意时刻桌面上同一种点数的牌至多只有一张。打出最后一张牌后,本局结束。

例如,桌面上的点数依次为 1,4,21,4,2。打出 33 后变为 1,4,2,31,4,2,3;再打出 44,会先收走原来的 4,2,34,2,3,再放上新打出的 44,此时桌面变为 1,41,4。

对于每个点数 i=1,2,…,mi=1,2,\ldots,m,请统计:在全部 nn 局游戏中,有多少局结束时桌面上留有点数为 ii 的牌。

输入格式

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

第一行输入两个正整数 n,mn,m,分别表示纸牌数量和点数种类数。

第二行输入 nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示从上到下各张牌的点数。

输出格式

输出到文件 card.out。

输出一行 mm 个非负整数,相邻整数用一个空格分隔。第 ii 个整数表示在全部 nn 局游戏中,有多少局结束时桌面上留有点数为 ii 的牌。

样例输入 1

4 3
1 2 1 3

样例输出 1

3 1 4

样例输入 2

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

样例输出 2

10 3 3

说明

样例 1 中,四局结束时桌面上的点数从左到右依次为:

  • 第 11 局:1,31,3;
  • 第 22 局:2,1,32,1,3;
  • 第 33 局:1,31,3;
  • 第 44 局:33。

因此,分别有 3,1,43,1,4 局结束时桌面上留有点数为 1,2,31,2,3 的牌。

评测数据规模

对于所有数据,保证:

  • 2≤n≤5×1052\le n\le5\times10^5,1≤m≤3×1051\le m\le3\times10^5;
  • 1≤ai≤m1\le a_i\le m;
  • 每种点数 1,2,…,m1,2,\ldots,m 都至少出现一次;
  • 所有输入数值均为整数。
测试点编号 n≤n\le m≤m\le 特殊性质
1∼31\sim3 55 22 无
4∼64\sim6 500500 200200
7∼97\sim9 50005000 30003000 A
10∼1210\sim12 无
13,1413,14 2×1052\times10^5 22
15∼1715\sim17 30003000 B
18,1918,19 无
2020 10510^5 A
21,2221,22 无
23∼2523\sim25 5×1055\times10^5 3×1053\times10^5

特殊性质 A:a1≤a2≤⋯≤ana_1\le a_2\le\cdots\le a_n。

特殊性质 B:至多有 49994999 个下标 ii 满足 ai≠ai+1a_i\ne a_{i+1}。

本题共 2525 个独立测试点,每点 44 分。

无金币奖励

CSP-J2026估分(民间数据)

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-10-31 17:00
结束于
2026-11-9 1:00
持续时间
200 小时
主持人
参赛人数
11