Frets On Fire
题意翻译
## 题目背景
Miyako 带着尤克里里琴来到跳蚤王国。她与当地的跳蚤居民成为了好朋友,每天为他们演奏美妙的音乐。
## 题目描述
作为回报,跳蚤为她做了一个更大的尤克里里琴:它有 $n$ 个弦,每个弦都有从 $0$ 到 $10^{18}$ 的 $10^{18}+1$ 个琴格(用来给琴划分音阶高低)。跳蚤使用数组 $s_1, s_2,......,s_n$ 来描述尤克里里琴的品,也就是说,第 $i$ 个弦上第 $j$ 个琴格的音调是整数 $s_i+j$。
Miyako 即将离开王国,但跳蚤希望 Miyako 能为它们回答最后一些问题。
第 $k$ 个问题是:“在所有弦上,琴格 $l_k$ 与琴格 $r_k$(包括 $l_k$,$r_k$)之间有多少个不同的音调?”
Miyako 即将访问蟋蟀王国,没有时间回答所有问题。请你帮助她完成这项任务!
在形式上,给出一个 $n$ 行 $10^{18}+1$ 列的矩阵,其中第 $i$ 行($1 \leqslant i \leqslant n$)第 $j$ 列($0 \leqslant j \leqslant 10^{18}$)中的单元格为整数 $s_i+j$。有 $q$ 个询问,对于第 $k$ 个询问,你需要回答矩阵中从第 $l_k$ 列到第 $r_k$ 列(包括 $l_k$,$r_k$)的不同整数的数量。
## 输入输出格式
### 输入格式
第一行包含整数 $n$($1 \leqslant n \leqslant 10^{5}$),表示弦的数量。
第二行包含 $n$ 个整数 $s_1,s_2,......s_n$
($0 \leqslant s_i \leqslant 10^{18}$),表示尤克里里琴的品。
第三行包含 $1$ 个整数 $q$($1 \leqslant q \leqslant 10^5$),表示问题的数量。
以下 $q$ 行中的第 $k$ 个包含两个整数 $l_k, r_k$
($0 \leqslant l_k \leqslant r_k \leqslant 10^{18}$),表示跳蚤的询问
### 输出格式
对于第 $k$ 个询问,输出一个整数,表示 $l_k$ 与 $r_k$ 之间不同音调的数量,每两个整数之间用空格分隔。
题目描述
Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.
In return, the fleas made a bigger ukulele for her: it has $ n $ strings, and each string has $ (10^{18} + 1) $ frets numerated from $ 0 $ to $ 10^{18} $ . The fleas use the array $ s_1, s_2, \ldots, s_n $ to describe the ukulele's tuning, that is, the pitch of the $ j $ -th fret on the $ i $ -th string is the integer $ s_i + j $ .
Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.
Each question is in the form of: "How many different pitches are there, if we consider frets between $ l $ and $ r $ (inclusive) on all strings?"
Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!
Formally, you are given a matrix with $ n $ rows and $ (10^{18}+1) $ columns, where the cell in the $ i $ -th row and $ j $ -th column ( $ 0 \le j \le 10^{18} $ ) contains the integer $ s_i + j $ . You are to answer $ q $ queries, in the $ k $ -th query you have to answer the number of distinct integers in the matrix from the $ l_k $ -th to the $ r_k $ -th columns, inclusive.
输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1 \leq n \leq 100\,000 $ ) — the number of strings.
The second line contains $ n $ integers $ s_1, s_2, \ldots, s_n $ ( $ 0 \leq s_i \leq 10^{18} $ ) — the tuning of the ukulele.
The third line contains an integer $ q $ ( $ 1 \leq q \leq 100\,000 $ ) — the number of questions.
The $ k $ -th among the following $ q $ lines contains two integers $ l_k $ , $ r_k $ ( $ 0 \leq l_k \leq r_k \leq 10^{18} $ ) — a question from the fleas.
输出格式
Output one number for each question, separated by spaces — the number of different pitches.
输入输出样例
输入样例 #1
6
3 1 4 1 5 9
3
7 7
0 2
8 17
输出样例 #1
5 10 18
输入样例 #2
2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000
输出样例 #2
2 1500000000000000000
说明
For the first example, the pitches on the $66$ strings are as follows.
$$\begin{matrix} \textbf{Fret} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \ldots \\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \dots \\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \dots \\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \dots \end{matrix}$$
There are $5$ different pitches on fret $7$ — $8, 10, 11, 12, 16$
There are $10$ different pitches on frets $0, 1, 2$ — $1, 2, 3, 4, 5, 6, 7, 9, 10, 11$