CF1520F2 Guess the K-th Zero (Hard version)

这是一个交互题。 这是该题的困难版本。与简单版本的区别在于，困难版本中 $1\le t\le \min(n,10^4)$，且查询次数限制为 $6\times 10^4$ 次。 Polycarp 正在玩一款电脑游戏。在这款游戏中，隐藏着一个由 $0$ 和 $1$ 组成的数组。如果 Polycarp 能够猜出从左往右第 $k$ 个 $0$ 的位置 $t$ 次，他就能获胜。 Polycarp 最多可以进行 $6\times 10^4$ 次如下类型的请求： - ? $l$ $r$ —— 查询区间 $[l, r]$（$1 \le l \le r \le n$）内所有元素之和。 为了让游戏更有趣，每当猜中一个 $0$ 时，该位置的 $0$ 会变成 $1$，游戏会在修改后的数组上继续进行。更正式地说，如果第 $k$ 个 $0$ 的位置是 $x$，那么在 Polycarp 猜中该位置后，数组的第 $x$ 个元素会从 $0$ 变为 $1$。 请帮助 Polycarp 赢得这场游戏。

首先，你的程序需要读取两个整数 $n$ 和 $t$（$1 \le n \le 2 \times 10^5$，$1\le t\le \min(n,10^4)$）。 接下来有 $t$ 行，每行包含一个整数 $k$（$1 \le k \le n$）。保证在每次请求时，数组中至少有 $k$ 个 $0$。你必须在输出当前 $k$ 的答案后，才能获得下一个 $k$ 的值。 之后，你最多可以进行 $6\times 10^4$ 次请求。 输出答案时请使用如下格式（这不是一次请求，不计入 $6\times 10^4$ 次限制）： - ! $x$ —— 表示第 $k$ 个 $0$ 的位置。 数组下标从 $1$ 到 $n$，从左到右编号。 输出完 $t$ 个答案后，你的程序应立即退出。 在本题中，交互器是非自适应的。这意味着在同一测试中，隐藏数组和查询不会发生变化。 如果请求格式错误，将会输出 $-1$。收到该值后，你的程序必须立即正常退出（例如调用 exit(0)），否则评测系统可能会给出任意判定。 如果请求次数超出限制，将会判定为 wrong answer。 如果你没有输出任何内容或忘记刷新输出缓冲区，可能会得到 Idleness limit exceeded 的判定。 在输出请求和换行符后，请立即刷新输出缓冲区： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 Hack 时请使用如下格式： 第一行输出字符串 $s$（$1 \le |s| \le 2 \times 10^5$），由 $0$ 和 $1$ 组成，以及整数 $t$（$1\le t\le \min(n,10^4)$）——即隐藏数组和请求次数。接下来 $t$ 行，每行输出一个整数 $k$（$1 \le k \le |s|$）。 被 Hack 的解答无法直接访问隐藏数组。

（见上文）

在样例中，隐藏数组一开始是 $[1,0,1,1,0,1]$。回答完 $k=2$ 的查询后，数组变成了 $[1,0,1,1,1,1]$。