CF1234B2 Social Network (hard version)

本题的简单版与困难版的唯一区别在于 $n$ 和 $k$ 的限制条件。 你正在通过智能手机在某个流行的社交网络上与朋友聊天。你的手机屏幕最多只能显示最近的 $k$ 个与你的朋友的会话。最开始，屏幕是空的（即显示的会话数为 $0$）。 每个会话都是你和某个朋友之间的。你和每个朋友之间最多只有一个会话。因此，每个会话可以通过朋友的编号唯一确定。 你突然拥有了预知未来的能力。你知道在一天中你将会收到 $n$ 条消息，第 $i$ 条消息来自编号为 $id_i$ 的朋友（$1 \le id_i \le 10^9$）。 如果你收到的消息来自当前屏幕上已经显示的 $id_i$ 的会话，则什么都不会发生：屏幕上的会话不会改变，也不会改变顺序，你只需阅读消息并继续等待下一条消息。 否则（即屏幕上没有 $id_i$ 的会话）： - 首先，如果屏幕上显示的会话数已经是 $k$，则移除最后一个（第 $k$ 个）会话。 - 现在，屏幕上的会话数一定小于 $k$，且 $id_i$ 的会话不在屏幕上。 - 将编号为 $id_i$ 的会话插入到屏幕的第一个（最上面）位置，其余会话依次向下移动一个位置。 你的任务是，在处理完所有 $n$ 条消息后，输出屏幕上显示的会话列表（按照显示顺序）。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 2 \times 10^5$），分别表示消息的数量和手机屏幕最多能显示的会话数。 第二行包含 $n$ 个整数 $id_1, id_2, \dots, id_n$（$1 \le id_i \le 10^9$），其中 $id_i$ 表示第 $i$ 条消息来自的朋友编号。

输出第一行包含一个整数 $m$（$1 \le m \le \min(n, k)$），表示处理完所有 $n$ 条消息后屏幕上显示的会话数量。 第二行输出 $m$ 个整数 $ids_1, ids_2, \dots, ids_m$，其中 $ids_i$ 表示处理完所有消息后，第 $i$ 个位置上显示的朋友编号。

在第一个样例中，会话列表的变化如下（每步从第一条到最后一条消息）： - $[]$； - $[1]$； - $[2, 1]$； - $[3, 2]$； - $[3, 2]$； - $[1, 3]$； - $[1, 3]$； - $[2, 1]$。 在第二个样例中，会话列表的变化如下： - $[]$； - $[2]$； - $[3, 2]$； - $[3, 2]$； - $[1, 3, 2]$； - 之后列表不再变化。 由 ChatGPT 4.1 翻译