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$ 的位置. 苏苏最多可以做 $ 6 \cdot 10^4 $ 次查询, 询问会返回一段区间和, 具体方式见输出格式. 为了让游戏更加一颗赛艇, 每次**猜到的 $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的程序不会直接得到你这个串.

题目描述

This is an interactive problem. This is a hard version of the problem. The difference from the easy version is that in the hard version $ 1 \le t \le \min(n, 10^4) $ and the total number of queries is limited to $ 6 \cdot 10^4 $ . Polycarp is playing a computer game. In this game, an array consisting of zeros and ones is hidden. Polycarp wins if he guesses the position of the $ k $ -th zero from the left $ t $ times. Polycarp can make no more than $ 6 \cdot 10^4 $ requests totally of the following type: - ? $ l $ $ r $ — find out the sum of all elements in positions from $ l $ to $ r $ ( $ 1 \le l \le r \le n $ ) inclusive. To make the game more interesting, each guessed zero turns into one and the game continues on the changed array. More formally, if the position of the $ k $ -th zero was $ x $ , then after Polycarp guesses this position, the $ x $ -th element of the array will be replaced from $ 0 $ to $ 1 $ . Help Polycarp win the game.

输入输出格式

输入格式

输出格式

First, your program must read two integers $ n $ and $ t $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le t \le \min(n, 10^4) $ ). Then $ t $ lines follow, each of which contains one integer $ k $ ( $ 1 \le k \le n $ ). It is guaranteed that at the moment of the request the array contains at least $ k $ zeros. In order to get the next value of $ k $ , you must output the answer for the previous value of $ k $ . After that, you can make no more than $ 6 \cdot 10^4 $ requests in total. Use the following format to output the answer (it is not a request, it doesn't count in $ 6 \cdot 10^4 $ ): - ! $ x $ — position of the $ k $ -th zero. Positions in the array are numbered from left to right from $ 1 $ to $ n $ inclusive. After printing $ t $ answers, your program should exit immediately. In this task, the interactor is not adaptive. This means that within the same test, the hidden array and the queries do not change. In case of an incorrect query, -1 will be displayed. When this value is received, your program must immediately exit normally (for example, by calling exit(0)), otherwise, the testing system may issue an arbitrary verdict. If the number of requests is exceeded, the verdict wrong answer will be displayed. Your solution may get the verdict Idleness limit exceeded if you don't print anything or forget to flush the output buffer. To flush the output buffer, you need to do the following immediately after the query output and the end-of-line character: - fflush(stdout) or cout.flush() in C ++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see the documentation for other languages. Hacks Use the following format for hacks: On the first line print the string $ s $ ( $ 1 \le |s| \le 2 \cdot 10^5 $ ), consisting of zeros and ones, and an integer $ t $ ( $ 1 \le t \le \min(|s|, 10^4) $ ) — hidden array and number of requests, respectively. In the next $ t $ lines output the number $ k $ ( $ 1 \le k \le |s| $ ). The hacked solution will not have direct access to the hidden array.

输入输出样例

输入样例 #1

6 2

2

2

1

1

0

1

0

输出样例 #1

? 4 6

? 1 1

? 1 2

? 5 5

! 5

? 2 2

! 2

说明

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] $ .