CF1520F2 Guess the K-th Zero (Hard version)

# Guess the K-th Zero (Hard version) **提示: 这是一道交互题**. 数据加强力! 与简化版相比, 现在数据范围比较巨大, $ 1 \le t \le \min(n, 10^4) $ , 而且你的询问次数不得超过 $ 6 \cdot 10^4 $ . 苏苏正在打电动. 她玩的游戏里, 有某个长度固定的 $0,1$ 序列. 苏苏需要在接下来的 $t$ 次操作中猜对从左到右第 $k$ 个 $0$ 的位置.

无

为了让游戏更加一颗赛艇, 每次**猜到的 $0$ 都会变成 $1$**, 然后游戏会在修改后的序列上继续进行. 换句话说, 如果第 $ k $ 个 $0$ 的位置是 $ x $ , 苏苏猜过了这个位置之后, 序列上第 $ 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$ 个 $0$ . 然后你可以做一些询问, 但是注意, 你的整个程序的**询问次数之和不能超过** $ 6 \cdot 10^4 $ 次. 询问形如: - `? l r` 交互库会返回 $[l,r] $ 元素的和 $ ( $ $1 \le l \le r \le n $ ) . 你觉得你这把稳了之后你就可以输出本轮操作的答案了. **注意: 你需要输出前一个操作的答案才能得到下一个 $ k $ 的值.** 回答形如: - `! x` 表示回答第 $ k $ 个 $0$ 的位置是 $x$ . 输出答案不会算进你的询问次数里: **规定位置为从左到右的 $ 1 $ 到 $ n $** . $t$ 次操作都结束之后, 你需要**马上正常退出程序**. 测试点的数据是固定的. 如果你某次回答错了, 你会收到交互库给你的信号 $-1$ , 此时你应该**马上程正常退出序**, 要不然交互库可能会给你点好果汁吃. 如果你询问太多, 同理. **注意: 请随时刷新输出缓冲区, 保证交互库可以正确得到你的回答或者询问.** 刷新方法如下: - `fflush(stdout)` or `cout.flush()` in C ++; - `System.out.flush()` in Java; - `flush(output)` in Pascal; - `stdout.flush()` in Python; - 没有举例的语言, ~~读者自查资料不难~~. ### 关于Hack方式 格式有限制: 第一行你先给出你的串 $ s $ ( $ 1 \le |s| \le 2 \cdot 10^5 $ ), 只能是 $0,1$ 串, 再给出一个整数 $ t $ ( $ 1 \le t \le \min(|s|, 10^4) $ ) 接下来 $ t $ 行给出你的 $ k $ ( $ 1 \le k \le |s| $ ). 被Hack的程序不会直接得到你这个串.

In the first test, the array $ [1, 0, 1, 1, 0, 1] $ is hidden. After answering the query $ k=2 $ , the array changed to $ [1, 0, 1, 1, 1, 1] $ .