CF2178E Flatten or Concatenate

这是一个交互题。 在工作中摸鱼的时候，妖精 Dilhan 偶然发现了两个数组 $a$ 和 $b$。最开始，它们都只包含一个整数 $2^k$（即 $a=b=[2^k]$），其中 $k$ 是一个非负整数。 Dilhan 随后对这两个数组进行了任意次数（可能为零），任意顺序的如下两种操作： 1. 扁平化（Flatten）—— 选择 $a$ 或 $b$ 中的一个数组，在数组中任选一个当前最大的元素 $x$（$x$ 不要求在另一个数组中也为最大）。然后，将 $x$ 替换为在同一位置上的两个 $\frac x 2$。该操作只能在 $x$ 为偶数时进行。 2. 拼接（Concatenate）—— 令 $a$ 和 $b$ 都变为 $a+b$，其中 $+$ 表示数组拼接操作。 在若干操作之后，Dilhan 丢弃了 $b$，并将 $a$ 隐藏起来，向你发起了挑战。 记隐藏数组 $a$ 的长度为 $n$。你可以进行以下询问： - 选择一个区间 $[l, r]$（$1\le l\le r\le n$），Dilhan 会告诉你 $a_l+a_{l+1}+\cdots+a_r$ 的值。 请在最多 $300$ 次询问中，确定 $a$ 中的最大元素的值。

每组测试包含多个测试用例。第一行包含测试用例数量 $t$（$1\le t\le 100$）。接下来的描述依次给出每个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1\le n\le 10^5$），表示数组 $a$ 的长度。 保证 $1\le a_i\le 2^{30}$，且该数组可由题目描述中的构造过程得到。 保证所有测试用例中 $n$ 之和不超过 $10^5$。

（交互题，请按照要求输出）

在第一个测试用例中，Dilhan 隐藏的数组 $a$ 是 $[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$。它的构造过程如下： | \# | 操作 | $a$ 操作后 | $b$ 操作后 | |:-:|:------------|:---------------------|:---------------------| | 0 | 初始 | $[4]$ | $[4]$ | | 1 | 对 $a$ 扁平化 | $[\underline 4] \to [2,2]$ | $[4]$ | | 2 | 对 $b$ 扁平化 | $[2,2]$ | $[\underline 4] \to [2,2]$ | | 3 | 对 $a$ 扁平化 | $[2,\underline 2] \to [2,1,1]$ | $[2,2]$ | | 4 | 拼接 | $[2,1,1,2,2]$ | $[2,1,1,2,2]$ | | 5 | 对 $a$ 扁平化 | $[\underline 2, 1, 1, 2, 2] \to [1,1,1,1,2,2]$ | $[2,1,1,2,2]$ | | 6 | 拼接 | $[1,1,1,1,2,2,2,1,1,2,2]$ | $[1,1,1,1,2,2,2,1,1,2,2]$ | - 询问 $\mathtt{?\;3\;8}$，回答为 $1+1+2+2+2+1=9$； - 询问 $\mathtt{?\;1\;4}$，回答为 $1+1+1+1=4$； - 询问 $\mathtt{?\;5\;11}$，回答为 $2+2+2+1+1+2+2=12$。 此时 $a$ 的最大元素为 $2$。 第二个测试用例中，数组 $a$ 只有一个元素。通过一次询问即可知道该元素的值，也就是最大值。 第三个测试用例中，Dilhan 隐藏的数组 $a$ 为 $[4, 4, 4, 4, 4, 4, 4, 4]$，其构造过程如下： | \# | 操作 | $a$ 操作后 | $b$ 操作后 | |:-:|:------------|:---------------------|:---------------------| | 0 | 初始 | $[4]$ | $[4]$ | | 1 | 拼接 | $[4,4]$ | $[4,4]$ | | 2 | 拼接 | $[4,4,4,4]$ | $[4,4,4,4]$ | | 3 | 拼接 | $[4,4,4,4,4,4,4,4]$ | $[4,4,4,4,4,4,4,4]$ | 最大元素为 $4$。 第四个测试用例中，Dilhan 隐藏的数组 $a$ 是 $[2^{29}, 2^{29}, 2^{30}, 2^{29}, 2^{28}, 2^{28}, 2^{29}, 2^{29}]$。 由 ChatGPT 5 翻译