CF2152D Division Versus Addition

对于一个长度为 $m$ 的数组 $b=[b_1,b_2,\ldots,b_m]$（$b_i \geq 2$），考虑由 Poby 和 Rekkles 进行的如下二人游戏： - 两位玩家轮流行动，Poby 先手。 - 在 Poby 的回合，他必须选择一个 $x \ge 2$ 的元素，将其替换为 $\left\lfloor \frac{x}{2} \right\rfloor$。也就是说，他选择 $i$（$1 \leq i \leq m$）且 $b_i \ge 2$，然后执行 $b_i := \left\lfloor \frac{b_i}{2} \right\rfloor$。 - 在 Rekkles 的回合，他必须选择数组 $b$ 中的一个 $x \ge 2$，并将其替换为 $x+1$。也就是说，他选择 $i$（$1 \leq i \leq m$）且 $b_i \ge 2$，然后执行 $b_i := b_i+1$。 当且仅当数组 $b$ 中所有元素都为 $1$ 时，游戏结束。 定义游戏的分数为 Poby 所做的操作次数。Poby 的目标是最小化分数，而 Rekkles 的目标是最大化分数。 对于数组 $b$，其值定义为在双方都采取最优策略时，此游戏的分数。 现在给定一个长度为 $n$ 的整数数组 $a$（$a_i \ge 2$）。 需要回答 $q$ 个独立的查询。每个查询给定一个范围 $1 \leq l \leq r \leq n$，你需要求出数组 $[a_l, a_{l+1}, \ldots, a_r]$ 的值。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。每组数据描述如下： 每组测试数据的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 250\,000$），分别表示数组 $a$ 的长度和查询的个数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$2 \le a_i \le 10^9$），表示数组 $a$ 的元素。 接下来的 $q$ 行，每行包含两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$），分别表示第 $j$ 个查询的子数组范围。 保证所有测试数据中 $n$ 的总和不超过 $250\,000$。 保证所有测试数据中 $q$ 的总和不超过 $250\,000$。

对于每个测试数据，请输出 $q$ 行答案。对于每个查询，输出一个整数，表示对应子数组的值。

第一组数据，第一个查询（1 1）的解释如下： 子数组为 $[4]$。 1. Poby: $4 \to \left\lfloor \tfrac{4}{2}\right\rfloor = 2$。数组变为 $[2]$。 2. Rekkles: $2 \to 3$。数组变为 $[3]$。 3. Poby: $3 \to \left\lfloor \tfrac{3}{2}\right\rfloor = 1$。数组变为 $[1]$，游戏结束。 可以证明，这种策略对双方都是最优的。因此，数组 $[4]$ 的值为 $2$。 第一组数据，第二个查询（1 2）的解释如下： 子数组为 $[4,3]$。 1. Poby: $3 \to \left\lfloor \tfrac{3}{2}\right\rfloor=1$。数组变为 $[4,1]$。 2. Rekkles: $4 \to 5$。数组变为 $[5,1]$。 3. Poby: $5 \to \left\lfloor \tfrac{5}{2}\right\rfloor=2$。数组变为 $[2,1]$。 4. Rekkles: $2 \to 3$。数组变为 $[3,1]$。 5. Poby: $3 \to \left\lfloor \tfrac{3}{2}\right\rfloor=1$。数组变为 $[1,1]$，游戏结束。 可以证明，这种策略对双方都是最优的。因此，数组 $[4,3]$ 的值为 $3$。 由 ChatGPT 5 翻译