P14046 [SDCPC 2019] BaoBao Loves Reading

BaoBao 是一位热爱读书的好学生，但与他那个装满了许多书的巨大书架相比，他的书桌却出奇地小，只能同时放下至多 $k$ 本书。 今天，BaoBao 决定在书桌旁读 $n$ 分钟的书。根据他的阅读计划，在第 $i$ 分钟，他计划阅读第 $a_i$ 本书。最开始，书桌上没有任何书，所有书都在书架上。如果 BaoBao 想要阅读的书不在书桌上，他就需要从书架上取出这本书。如果书桌已经满了，而 BaoBao 又需要从书架上拿新的书，那么他必须先把书桌上的某本书放回书架，然后才能拿新书。 BaoBao 不想纠结选择哪本书放回书架，于是在网上查到了一个叫做「最近最少使用」（Least Recently Used，LRU）算法。根据该算法，BaoBao 放回书架的应该是「距离现在最久未被阅读」的那本书。 例如，考虑阅读计划 $\{4, 3, 4, 2, 3, 1, 4\}$，假设书桌容量为 3。下表说明了按 LRU 算法 BaoBao 应该怎么做。下面表格中，用整数对 $(a, b)$ 表示一本书，$a$ 是该书的编号，$b$ 是上次被阅读的时间。 $$ \begin{array}{|c|c|c|} \hline \textbf{第几分钟} & \textbf{当前书桌上的书} & \textbf{BaoBao 的操作} \\ & \textbf{（进入此分钟前）} & \\ \hline 1 & \{\} & \text{从书架取书 4}\\ \hline 2 & \{(4, 1)\} & \text{从书架取书 3} \\ \hline 3 & \{(4, 1), (3, 2)\} & \text{无需操作，书 4 已在书桌} \\ \hline 4 & \{(4, 3), (3, 2)\} & \text{从书架取书 2} \\ \hline 5 & \{(4, 3), (3, 2), (2, 4)\} & \text{无需操作，书 3 已在书桌} \\ \hline 6 & \{(4, 3), (3, 5), (2, 4)\} & \text{将最久未被阅读的书 4 放回书架，从书架取书 1} \\ \hline 7 & \{(3, 5), (2, 4), (1, 6)\} & \text{将最久未被阅读的书 2 放回书架，从书架取书 4} \\ \hline \end{array} $$ 现给出阅读计划，请你计算当书桌容量 $k$ 依次取 $1$ 到 $n$（均包含）的值时，BaoBao 总共需要从书架取书的次数。

有多组测试数据。输入的第一行为一个整数 $T$，表示测试用例的个数。 对于每组测试数据： 第一行为一个整数 $n$（$1 \le n \le 10^5$），表示阅读计划的长度。 第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示每分钟要阅读的书的编号。 保证所有测试数据中 $n$ 的总和不超过 $10^6$。

对于每组测试数据，输出一行，包含 $n$ 个用空格分隔的整数 $f_1, f_2, \dots, f_n$，其中 $f_i$ 表示当书桌容量为 $i$ 时，BaoBao 从书架上取书的总次数。 注意，行末不要输出多余的空格，否则答案会被判为错误！

由 ChatGPT 5 翻译