AT_pakencamp_2024_day2_d Double Mochi

在パケン国，有在新年伊始竖直堆放年糕作为吉祥物“ダブル餅”的习俗。这种“ダブル餅”具有以下性质： - 假设自上而下堆叠的年糕重量依次为 $V_1, V_2, \dots, V_n$（一共有 $n$ 个年糕），那么对于所有的 $i$（$1 \leq i \leq n-1$），都有 $2 \times V_i \leq V_{i+1}$ 成立。 パケン国的居民パケ子拥有编号从 $1$ 到 $N$ 的 $N$ 个年糕。第 $i$ 个年糕（$1 \leq i \leq N$）的重量是 $W_i$。对于所有 $i$（$1 \leq i \leq N-1$），都有 $W_i \leq W_{i+1}$。パケ子会向你提出 $Q$ 个询问。第 $i$ 个询问内容为：“如果选用编号从 $L_i$ 到 $R_i$ 的所有年糕，每种各用一次，制作若干个ダブル餅，最少需要制作多少个ダブル餅？” 请分别回答每个询问的最小个数。

输入通过标准输入给出，格式如下： > $N$ $Q$ $W_1$ $W_2$ $\ldots$ $W_N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

## 子任务 1. （1 分）$N \leq 6$，$Q = 1$ 2. （4 分）$N \leq 16$，$Q = 1$ 3. （10 分）$N \leq 2000$，$Q = 1$ 4. （10 分）$Q = 1$ 5. （75 分）无额外限制 ## 样例解释 1 第 $1$ 个询问，对应使用的年糕重量分别为 $3, 4, 6, 8, 16$。 - 用重量为 $3$ 和 $6$ 的年糕组成一个ダブル餅； - 用重量为 $4, 8, 16$ 的年糕组成一个ダブル餅。 这样一共可以用 $2$ 个ダブル餅完成，且为最少。 第 $2$ 个询问，只用重量为 $3$ 的年糕。这种情况下必须制作 $1$ 个ダブル餅。 注意即使只有一个年糕，它本身也可以作为一个合法的ダブル餅。 第 $3$ 个询问，使用的年糕重量分别为 $2, 3, 3, 4, 6, 8, 16$。 - 用重量为 $3$ 和 $6$ 的年糕组成一个ダブル餅； - 用重量为 $2, 4, 8, 16$ 的年糕组成一个ダブル餅； - 剩下的一个 $3$ 单独作为一个ダブル餅。 这样一共可以用 $3$ 个ダブル餅完成，且为最少。 本样例满足子任务 $5$ 的约束条件。 # 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq W_i \leq 10^9$（$1 \leq i \leq N$） - $1 \leq L_i \leq R_i \leq N$（$1 \leq i \leq Q$） - $W_i \leq W_{i+1}$（$1 \leq i \leq N-1$） - 输入均为整数。 由 ChatGPT 5 翻译