← 返回题目列表

Codeforces · 1520/F2

F2. 猜第 K 个零(困难版)

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

这是一个交互问题。

这是问题的困难版本。与简单版本的区别在于,在困难版本中 $$$1 \le t \le \min(n, 10^4)$$$ 并且查询总数限制为 $$$6 \cdot 10^4$$$。

Polycarp 正在玩电脑游戏。在这个游戏中,隐藏了一个由 0 和 1 组成的数组。如果波利卡普猜出左边第 $$$k$$$ 次零的位置 $$$t$$$ 次,他就获胜。

Polycarp 最多可以发出不超过 $$$6 \cdot 10^4$$$ 的以下类型请求:

- ? $$$l$$$ $$$r$$$ — 找出从 $$$l$$$ 到 $$$r$$$ ($$$1 \le l \le r \le n$$$) 位置的所有元素的总和。

为了让游戏更有趣,每个猜测的零都会变成一,并且游戏在改变的数组上继续。更正式地说,如果第 $$$k$$$ 个零的位置是 $$$x$$$,那么在 Polycarp 猜测这个位置后,数组的第 $$$x$$$ 个元素将从 $$$0$$$ 替换为 $$$1$$$。

帮助波利卡普赢得比赛。

互动

首先,你的程序必须读取两个整数 $$$n$$$ 和 $$$t$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le t \le \min(n, 10^4)$$$)。

接下来是 $$$t$$$ 行,每一行包含一个整数 $$$k$$$ ($$$1 \le k \le n$$$)。保证在请求时数组至少包含 $$$k$$$ 个零。为了获得 $$$k$$$ 的下一个值,您必须输出 $$$k$$$ 的前一个值的答案。

此后,您总共可以发出不超过 $$$6 \cdot 10^4$$$ 请求。

使用以下格式输出答案(这不是请求,它不会计入 $$$6 \cdot 10^4$$$):

- ! $$$x$$$ — 第 $$$k$$$ 个零的位置。

数组中的位置从左到右编号,从 $$$1$$$ 到 $$$n$$$(含)。

打印 $$$t$$$ 答案后,你的程序应该立即退出。

在此任务中,交互器不具有自适应性。这意味着在同一测试中,隐藏数组和查询不会改变。

如果查询错误,将显示-1。当收到此值时,您的程序必须立即正常退出(例如,通过调用 exit(0)),否则,测试系统可能会发出任意判决。

如果超过请求次数,将显示判定错误答案。

如果您不打印任何内容或忘记刷新输出缓冲区,您的解决方案可能会得到超出空闲限制的判决。

要刷新输出缓冲区,您需要在查询输出和行尾字符之后立即执行以下操作:

- C ++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

使用以下格式进行黑客攻击:

在第一行打印字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$),由零和一组成,以及一个整数 $$$t$$$ ($$$1 \le t \le \min(|s|, 10^4)$$$) - 分别是隐藏数组和请求数。在接下来的 $$$t$$$ 行中输出数字 $$$k$$$ ($$$1 \le k \le |s|$$$)。

被黑客攻击的解决方案将无法直接访问隐藏数组。

示例

输入 #1

6 2

2

2

1

1

0

1

0

输出 #1

? 4 6

? 1 1

? 1 2

? 5 5

! 5

? 2 2

! 2

注意

在第一个测试中,数组 $$$[1, 0, 1, 1, 0, 1]$$$ 被隐藏。回答查询$$$k=2$$$后,数组变为$$$[1, 0, 1, 1, 1, 1]$$$。