#P12646. [KOI 2024 Round 1] 升序

[KOI 2024 Round 1] 升序

题目背景

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个长度为 MM 的正整数序列 X1,X2,,XMX_1, X_2, \dots, X_M,我们希望将这个序列变为升序。一个序列 X1,X2,,XMX_1, X_2, \dots, X_M 是升序的,当且仅当对所有 ii1iM11 \leq i \leq M - 1)满足 XiXi+1X_i \leq X_{i+1}

为了将序列 XX 变为升序,可以对其应用如下操作任意次数(包括 00 次):

  • 对于某个 ii1iM1 \leq i \leq M),将 XiX_i 乘以 22

我们将通过最少的操作次数将 XX 变为升序时所需的操作次数记为 f(X)f(X)

现在,给定一个长度为 NN 的正整数序列 A1,A2,,ANA_1, A_2, \dots, A_N,以及 QQ 个查询。每个查询给出两个整数 llrr,满足 1lrN1 \leq l \leq r \leq N。查询的目标是计算 f(Al,Al+1,,Ar)f(A_l, A_{l+1}, \dots, A_r),即将从 AA 中截取的子序列升序所需的最小操作次数。

请计算并输出每个查询的答案。

输入格式

第一行输入两个整数 NNQQ,用空格分隔。
第二行输入 NN 个整数 A1,A2,,ANA_1, A_2, \dots, A_N,用空格分隔。
接下来的 QQ 行,每行输入两个整数 llrr,表示一次查询。

输出格式

输出 QQ 行,第 ii 行输出第 ii 个查询的答案。

10 5
5 2 7 3 2 9 6 3 3 5
3 9
1 10
1 8
2 4
8 9
14
27
19
2
0
10 5
2 8 4 9 10 8 5 3 7 7
2 8
1 10
3 3
1 3
8 10
7
11
0
1
0

提示

约束条件

  • 所有输入均为整数。
  • 1N2500001 \leq N \leq 250\,000
  • 1Q2500001 \leq Q \leq 250\,000
  • 1Ai109(1iN)1 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)
  • 对所有查询满足 1lrN1 \leq l \leq r \leq N

子问题

1.(5 分)N10000, Q10000N \leq 10\,000,\ Q \leq 10\,000
2.(7 分)N10000N \leq 10\,000
3.(28 分)所有查询满足 r=Nr = N
4.(10 分)对所有 ii 满足 AiAi+1A_i \geq A_{i+1}
5.(5 分)对所有 ii 满足 Ai2A_i \leq 2
6.(10 分)对所有 ii 存在非负整数 kik_i 使得 Ai=2kiA_i = 2^{k_i}
7.(35 分)无额外限制条件

翻译由 ChatGPT-4o 完成