P12646 [KOI 2024 Round 1] 升序

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

给定一个长度为 $M$ 的正整数序列 $X_1, X_2, \dots, X_M$，我们希望将这个序列变为升序。一个序列 $X_1, X_2, \dots, X_M$ 是升序的，当且仅当对所有 $i$（$1 \leq i \leq M - 1$）满足 $X_i \leq X_{i+1}$。 为了将序列 $X$ 变为升序，可以对其应用如下操作任意次数（包括 $0$ 次）： - 对于某个 $i$（$1 \leq i \leq M$），将 $X_i$ 乘以 $2$。 我们将通过最少的操作次数将 $X$ 变为升序时所需的操作次数记为 $f(X)$。 现在，给定一个长度为 $N$ 的正整数序列 $A_1, A_2, \dots, A_N$，以及 $Q$ 个查询。每个查询给出两个整数 $l$ 和 $r$，满足 $1 \leq l \leq r \leq N$。查询的目标是计算 $f(A_l, A_{l+1}, \dots, A_r)$，即将从 $A$ 中截取的子序列升序所需的最小操作次数。 请计算并输出每个查询的答案。

第一行输入两个整数 $N$ 和 $Q$，用空格分隔。 第二行输入 $N$ 个整数 $A_1, A_2, \dots, A_N$，用空格分隔。 接下来的 $Q$ 行，每行输入两个整数 $l$ 和 $r$，表示一次查询。

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

**约束条件** - 所有输入均为整数。 - $1 \leq N \leq 250\,000$ - $1 \leq Q \leq 250\,000$ - $1 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$ - 对所有查询满足 $1 \leq l \leq r \leq N$ **子问题** 1.（5 分）$N \leq 10\,000,\ Q \leq 10\,000$ 2.（7 分）$N \leq 10\,000$ 3.（28 分）所有查询满足 $r = N$ 4.（10 分）对所有 $i$ 满足 $A_i \geq A_{i+1}$ 5.（5 分）对所有 $i$ 满足 $A_i \leq 2$ 6.（10 分）对所有 $i$ 存在非负整数 $k_i$ 使得 $A_i = 2^{k_i}$ 7.（35 分）无额外限制条件 翻译由 ChatGPT-4o 完成