解题思路

设 $p_x,c_x$ 分别为点数 $x$ 的末次出现位置和出现次数，约定 $a_{n+1}=0,p_0=n+1$。

任意以 $x$ 开局，处理至 $p_x$ 时桌面均仅剩 $x$，故最终序列为 $x$ 接上后缀 $[p_x+1,n]$ 的最终序列。连边：

$$x\to a_{p_x+1}$$

沿边 $p$ 严格递增，形成以 $0$ 为根的树。每局最终牌值恰为 $a_i$ 到根路径上的非 $0$ 结点，故答案是以 $c_x$ 为权的子树和。按 $p_x$ 递增向父亲累加即可，时间复杂度为 $O(n+m)$。

参考代码

365 Bcpp

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
int a[N],last[N],ans[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		last[a[i]]=i;
		ans[a[i]]++;
	}
	for(int i=1;i<=n;i++)if(last[a[i]]==i)ans[a[i+1]]+=ans[a[i]];
	for(int i=1;i<=m;i++)cout<<ans[i]<<' ';
	return 0;
}