AT_abc305_d [ABC305D] Sleep Log

题目描述

高桥君正在记录自己的睡眠情况。睡眠记录用一个奇数长度的数列 $A=(A_1(=0), A_2, \ldots, A_N)$ 表示，奇数下标表示起床时间，偶数下标表示入睡时间。更严格地说，在记录期间，高桥君的睡眠情况如下：

• 对于所有满足 $1\leq i\leq\dfrac{N-1}{2}$ 的整数 $i$，高桥君在开始记录后的第 $A_{2i}$ 分钟正好入睡，在第 $A_{2i+1}$ 分钟正好醒来。
• 除此之外的时间段内，高桥君既没有入睡也没有醒来。

请回答接下来的 $Q$ 个询问。第 $i$ 个询问给出一组整数 $(l_i, r_i)$，满足 $0\leq l_i\leq r_i\leq A_N$。

• 从开始记录后的第 $l_i$ 分钟到第 $r_i$ 分钟这 $r_i-l_i$ 分钟内，高桥君睡着了多少分钟？

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_Q$ $r_Q$

输出格式

请输出 $Q$ 行，每行输出第 $i$ 个询问的答案，结果为整数。

输入输出样例 #1

输入 #1

7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160

输出 #1

480
0
960

输入输出样例 #2

输入 #2

21
0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000
10
77 721
255 541
478 970
369 466
343 541
42 165
16 618
222 592
730 983
338 747

输出 #2

296
150
150
49
89
20
279
183
61
177

说明/提示

限制条件

• $3\leq N<2\times10^5$
• $N$ 是奇数
• $0=A_1<A_2<\cdots<A_N\leq10^9$
• $1\leq Q\leq2\times10^5$
• $0\leq l_i\leq r_i\leq A_N\ (1\leq i\leq Q)$
• 输入均为整数

样例解释 1

高桥君的睡眠情况如下图所示。

每个询问的答案如下：

• 从记录开始后第 $480$ 分钟到第 $1920$ 分钟，高桥君在 $480$ 分钟到 $720$ 分钟、$1320$ 分钟到 $1440$ 分钟、$1800$ 分钟到 $1920$ 分钟这三段时间睡觉。总睡眠时间为 $240+120+120=480$ 分钟。
• 从 $720$ 分钟到 $1200$ 分钟期间，高桥君没有睡觉。总睡眠时间为 $0$ 分钟。
• 从 $0$ 分钟到 $2160$ 分钟期间，高桥君在 $240$ 分钟到 $720$ 分钟、$1320$ 分钟到 $1440$ 分钟、$1800$ 分钟到 $2160$ 分钟这三段时间睡觉。总睡眠时间为 $480+120+360=960$ 分钟。

因此，分别输出 $480, 0, 960$。

由 ChatGPT 4.1 翻译