分数: 575 点
问题陈述
有 N 麻糬(年糕),按大小升序排列。 尺寸 i-第麻糬 (1\leq i\leq N) is A_i.
给了两个麻糬 A 和 B,有尺寸 a 和 b 分别,您可以通过放置麻糬来制作一个镜饼(一种堆叠的年糕) A 在麻糬上面 B 当且仅当 a 最多为一半 b.
你被给予 Q 整数对。让 (L_i, R_i) 是 i第对 (1\leq i\leq Q),并为每个解决以下问题 i:
仅使用 R_i - L_i + 1 麻糬来自 L_i-第 R_i-th,你可以同时制作多少个镜饼?
更准确地说,找到最大非负整数 K 这样:
- 出 R_i - L_i + 1 麻糬来自 L_i-第 R_i-th,选择 2K 麻糬和表格 K 对。对于每一对,将一个麻糬放在另一个上面,以制作 K 镜饼。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
- A_i \leq A_{i+1} \ (1 \leq i < N)
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq L_i < R_i \leq N \ (1 \leq i \leq Q)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dotsc A_N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
输出
打印 Q 行。的 i第行 (1\leq i\leq Q) 应包含以下问题的答案 i-第一个查询。
示例输入 1
11 1 1 2 3 4 4 7 10 11 12 20 5 2 5 3 8 7 11 1 2 1 11
示例输出 1
2 3 1 0 5
每个查询的答案如下。每个查询都给出了一种制作镜饼的可能方法。
- 麻糬尺寸为 (1, 2, 3, 4)。你可以做两个镜饼 (1,3) 和 (2,4).
- 麻糬尺寸为 (2, 3, 4, 4, 7, 10)。你可以做三个镜饼 (2,4), (3,7),和 (4,10).
- 麻糬尺寸为 (7, 10, 11, 12, 20)。你可以制作一份镜饼 (10,20).
- 麻糬尺寸为 (1, 1)。你无法制作镜饼。
- 麻糬尺寸为 (1, 1, 2, 3, 4, 4, 7, 10, 11, 12, 20)。可以做五个镜饼 (1,2), (1,3), (4,10), (4,11),和 (7,20).
因此,打印 2, 3, 1, 0, 5 按此顺序。
示例输入 2
24 127 148 170 174 258 311 331 414 416 436 517 523 532 587 591 638 660 748 760 776 837 857 972 984 15 7 11 8 9 8 13 12 15 9 23 1 17 8 12 1 5 6 17 3 7 12 19 13 18 7 22 1 12 14 15
示例输出 2
0 0 0 0 2 6 0 1 1 0 0 0 3 5 0