← 返回题目列表

AtCoder · abc388_g

G. 同时镜饼2

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

分数: 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