Sleep Log

题目描述

Takahashi 记录着一份睡眠日志。 该日志表示为一个奇数长度的序列 $A=(A _ 1(=0), A _ 2,\ldots,A _ N)$，其中奇数下标的元素表示他起床的时间，偶数下标的元素表示他睡觉的时间。 更正式地说，在开始记录睡眠日志后，他有如下的睡眠区间。

对于每个整数 $i$ 满足 $1\leq i\leq\dfrac{N-1}2$，他在开始记录睡眠日志后恰好 $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$ 分钟内，Takahashi 总共睡了多少分钟？

输入格式

输入从标准输入给出，格式如下： $N$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$ $Q$ $l _ 1$ $r _ 1$ $l _ 2$ $r _ 2$ $\vdots$ $l _ Q$ $r _ Q$

输出格式

输出 $Q$ 行答案。 第 $i$ 行应包含回答第 $i$ 个问题的整数。

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

480
0
960

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

296
150
150
49
89
20
279
183
61
177

提示

$3\leq N\lt2\times10^5$ $N$ 是奇数。 $0=A _ 1\lt A _ 2\lt\cdots\lt 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)$ 所有输入值均为整数。Takahashi 的睡眠如下面的图所示。 每个问题的答案如下。

在开始记录睡眠日志后 $480$ 分钟到 $1920$ 分钟之间，Takahashi 在 $480$ 分钟到 $720$ 分钟、$1320$ 分钟到 $1440$ 分钟、以及 $1800$ 分钟到 $1920$ 分钟有 $3$ 次睡眠。总睡眠时间为 $240+120+120=480$ 分钟。 在开始记录睡眠日志后 $720$ 分钟到 $1200$ 分钟之间，Takahashi 没有睡觉。总睡眠时间为 $0$ 分钟。 在开始记录睡眠日志后 $0$ 分钟到 $2160$ 分钟之间，Takahashi 在 $240$ 分钟到 $720$ 分钟、$1320$ 分钟到 $1440$ 分钟、以及 $1800$ 分钟到 $2160$ 分钟有 $3$ 次睡眠。总睡眠时间为 $480+120+360=960$ 分钟。

因此，输出的三行应分别为 $480$、$0$ 和 $960$.

标签: AtCoder|abc305D

来源

AtCoder|abc305D