解题思路

令 $T_i$ 表示第 $i$ 局最终桌面的点数集合，$u_i$ 表示 $i$ 右侧最近的 $a_i$ 位置；若不存在，则 $u_i=0$，并约定 $T_{n+1}=\varnothing$。若 $u_i>0$，处理到 $u_i$ 会清空桌面并重新放上 $a_i$；否则 $a_i$ 会保留。因此：

$$T_i= \begin{cases} T_{u_i} & u_i>0 \\ T_{i+1}\cup\set{a_i} & u_i=0 \end{cases}$$

倒序构造链表，链首为 $rt_i$：$u_i>0$ 时复用 $rt_{u_i}$，否则新建 $a_i$ 结点并接到 $rt_{i+1}$。每个 $rt_i$ 计数一次；结点按倒序创建，后继编号更小，故按编号递减传递计数。$k$ 的末次出现结点计数即答案，复杂度为 $O(n+m)$。

参考代码

557 Bcpp

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

const int N=500005;
int a[N],last[N],rt[N],nxt[N],id[N],cnt[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];
	int tot=0;
	for(int i=n;i>=1;i--)
	{
		if(last[a[i]])rt[i]=rt[last[a[i]]];
		else
		{
			tot++;
			id[a[i]]=tot;
			nxt[tot]=rt[i+1];
			rt[i]=tot;
		}
		last[a[i]]=i;
	}
	for(int i=1;i<=n;i++)cnt[rt[i]]++;
	for(int i=tot;i>=1;i--)cnt[nxt[i]]+=cnt[i];
	cout<<cnt[id[1]];
	for(int i=2;i<=m;i++)cout<<' '<<cnt[id[i]];
	return 0;
}