← 返回题目列表

Codeforces · 1234/B2

B2. 社交网络(硬版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是对 $$$n$$$ 和 $$$k$$$ 的约束。

您正在通过智能手机在流行的社交网络之一中发送消息。您的智能手机最多可以显示 $$$k$$$ 最近与朋友的对话。最初,屏幕是空的(即显示的对话数量等于 $$$0$$$)。

每次对话都是您和您的一些朋友之间的。与您的任何朋友最多有一次对话。因此,每次对话都是由您的朋友独特定义的。

你(突然间!)有能力看到未来。您知道白天您将收到 $$$n$$$ 消息,其中第 $$$i$$$ 消息将从 ID 为 $$$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 \cdot 10^5)$$$ — 您的智能手机可以显示的消息数和对话数。

输入的第二行包含 $$$n$$$ 整数 $$$id_1, id_2, \dots, id_n$$$ ($$$1 \le id_i \le 10^9$$$),其中 $$$id_i$$$ 是向您发送第 $$$i$$$ 条消息的好友 ID。

输出

在输出的第一行打印一个整数 $$$m$$$ ($$$1 \le m \le min(n, k)$$$) — 收到所有 $$$n$$$ 消息后显示的对话数。

第二行打印 $$$m$$$ 整数 $$$ids_1, ids_2, \dots, ids_m$$$,其中 $$$ids_i$$$ 应该等于接收到所有 $$$n$$$ 消息后 $$$i$$$ 位置上显示的对话对应的好友 ID。

示例

输入 #1

7 2
1 2 3 2 1 3 2

输出 #1

2
2 1

输入 #2

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

输出 #2

3
1 3 2

注意

在第一个示例中,对话列表将按以下方式更改(按从第一条消息到最后一条消息的顺序):

- $$$[]$$$;
- $$$[1]$$$;
- $$$[2, 1]$$$;
- $$$[3, 2]$$$;
- $$$[3, 2]$$$;
- $$$[1, 3]$$$;
- $$$[1, 3]$$$;
- $$$[2, 1]$$$.

在第二个示例中,对话列表将按以下方式更改:

- $$$[]$$$;
- $$$[2]$$$;
- $$$[3, 2]$$$;
- $$$[3, 2]$$$;
- $$$[1, 3, 2]$$$;
- 然后列表直到最后都不会改变。