CF1290D Coffee Varieties (hard version)

这是该问题的困难版本。你可以在 Div. 2 比赛中找到简单版本。两个版本的区别仅在于你可以让朋友品尝咖啡的次数不同。 这是一个交互题。 你正在考虑搬到另一个城市，你的一个朋友已经住在那里。这个城市有 $n$ 家咖啡馆，其中 $n$ 是 $2$ 的幂次。第 $i$ 家咖啡馆只生产一种咖啡 $a_i$。 作为咖啡爱好者，在决定是否搬家之前，你想知道这个城市一共有多少种不同的咖啡品种 $d$。 你并不知道 $a_1, \ldots, a_n$ 的具体数值。幸运的是，你的朋友有一个容量为 $k$ 的记忆力，其中 $k$ 也是 $2$ 的幂次。 你每天可以让他品尝一家咖啡馆 $c$ 的咖啡，他会告诉你在过去 $k$ 天内是否品尝过类似的咖啡。 你还可以让他服用一种药物来重置记忆。他会忘记之前品尝过的所有咖啡。你最多可以重置记忆 $30\,000$ 次。 更正式地说，你朋友的记忆是一个队列 $S$。对咖啡馆 $c$ 进行一次查询会： - 告诉你 $a_c$ 是否在 $S$ 中； - 将 $a_c$ 加入 $S$ 的队尾； - 如果 $|S| > k$，则弹出 $S$ 的队首元素。 进行一次重置操作会清空 $S$ 中的所有元素。 你的朋友最多可以品尝 $\dfrac{3n^2}{2k}$ 杯咖啡。请你找出不同咖啡品种的数量 $d$（即数组 $a$ 中不同数值的个数）。 注意，某些测试点中交互器的行为是自适应的。这意味着数组 $a$ 在交互开始前可能不是固定的，并且可能会根据你的查询动态变化。保证在交互的任何时刻，至少存在一个数组 $a$ 与所有已给出的答案一致。

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 1024$，$k$ 和 $n$ 都是 $2$ 的幂次）。 保证 $\dfrac{3n^2}{2k} \le 15\,000$。

你通过读取 $n$ 和 $k$ 开始交互。 - 若要让你的朋友品尝第 $c$ 家咖啡馆的咖啡，在单独一行输出 `? c`，其中 $1 \le c \le n$。不要忘记刷新输出以获得答案。 作为回应，你会收到一个字母 Y（是）或 N（否），表示这种咖啡品种 $a_c$ 是否在他记忆的最近 $k$ 种咖啡中。 - 若要重置你朋友的记忆，在单独一行输出大写字母 `R`。你最多可以进行 $30\,000$ 次重置操作。 - 当你确定不同咖啡品种的数量 $d$ 时，输出 `! d`。 如果你的查询无效，或者你进行了超过 $\frac{3n^2}{2k}$ 次 `?` 查询，或超过 $30\,000$ 次 `R` 查询，程序会输出字母 `E` 并结束交互。你将收到 Wrong Answer 判定。请确保立即退出以避免获得其他判定。 每次输出查询后不要忘记换行并刷新输出，否则会因超时被判为 Idleness limit exceeded。具体刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档。 Hack 格式 第一行应为单词 `fixed`。 第二行包含两个整数 $n$ 和 $k$，用空格分隔（$1 \le k \le n \le 1024$，$k$ 和 $n$ 都是 $2$ 的幂次）。 必须满足 $\dfrac{3n^2}{2k} \le 15\,000$。 第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，用空格分隔（$1 \le a_i \le n$）。

在第一个示例中，数组为 $a = [1, 4, 1, 3]$。这个城市一共生产 $3$ 种不同的咖啡品种（$1$、$3$ 和 $4$）。 你朋友依次品尝的咖啡品种为 $1, 4, \textbf{1}, 3, 3, 1, 4$（加粗的答案对应 Y）。注意，在两次 `? 4` 查询之间有一次记忆重置操作 `R`，所以第二次 `? 4` 的答案是 N。如果没有重置操作，第二次 `? 4` 的答案就是 Y。 在第二个示例中，数组为 $a = [1, 2, 3, 4, 5, 6, 6, 6]$。这个城市一共生产 $6$ 种不同的咖啡品种。 你朋友依次品尝的咖啡品种为 $2, 6, 4, 5, \textbf{2}, \textbf{5}$。 由 ChatGPT 4.1 翻译