← 返回题目列表

AtCoder · pakencamp_2024_day2_d

D. 双麻糬

中文机器翻译题面 查看原题

配点 : 100 点

問題文

在巴肯,有在年初展示“双麻糬”的习俗,这是一种将麻糬垂直堆叠而成的幸运符。这种双麻糬具有以下特性。

  • 计算从上到下堆叠的每个麻糬的重量。 V_1, V_2, \dots, V_n(麻糬的数量是 n ),然后全部 i (1 \leq i \leq n-1)对于 2 \times V_i \leq V_{i+1} 成立。

Pakeko,Pakken 国家的居民, 我有 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 如果您使用每个数字仅使用一个麻糬来制作多个双麻糬,您会制作多少个双麻糬? ”是内容,请回答每项所需的最少数量。

制約

  • 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)
  • 所有输入均为整数

小課題

  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 点)无附加约束 打印第

入力

输入是按以下格式从标准输入给出的。

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

7 3
2 3 3 4 6 8 16
3 7
2 2
1 7

出力例 1

2
1
3

1 次查询中,使用的每个年糕的重量为 3,4,6,8,16 。

  • 重量为 使用 3 和 按字典顺序比较 6 麻糬的双麻糬
  • 重量为 使用 4,8,16 麻糬的双麻糬

像这样 2 制作一份双麻糬,制作的双麻糬数量为 2 件,这是最少的。 在第

2 次查询中,使用的麻糬的重量为 仅 3 。在这种情况下,制作双麻糬的数量必须是 将会有 1 块。
麻糬 1 请注意,即使只有一个麻糬本身也被视为双麻糬。

3 次查询中,使用的每个年糕的重量为 2,3,3,4,6,8,16 。

  • 重量为 使用 3 和 按字典顺序比较 6 麻糬的双麻糬
  • 重量为 使用 2,4,8,16 麻糬的双麻糬
  • 重量为 使用 3 由单个麻糬组成的双麻糬 通过制作

像这样 3 双麻糬,制作的双麻糬数量为 3 件,这是最少的。 在第
此示例是一个小作业。 5 约束。