Codeforces Global Round 2-D. Frets On Fire-2점

Codeforces Global Round 2-D. Frets On Fire-2점
【Description】

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 (1018+1) frets numerated from 0 to 1018. The fleas use the array s1,
s2,…,sn to describe the ukulele's tuning, that is, the pitch of the j-th fret 
on the i-th string is the integer si+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 (1018+1) columns, where the 
cell in the i-th row and j-th column (0≤j≤1018) contains the integer si+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 lk-th to the rk-th columns, inclusive.

【Input】

The first line contains an integer n (1≤n≤100000) — the number of strings.

The second line contains n integers s1,s2,…,sn (0≤si≤1018) — the tuning of the 
ukulele.

The third line contains an integer q (1≤q≤100000) — the number of questions.

The k-th among the following q lines contains two integers lk，rk (0≤lk≤rk≤1018)
— a question from the fleas.

【Output】

Output one number for each question, separated by spaces — the number of 
different pitches.

【Examples】
Sample Input

6
3 1 4 1 5 9
3
7 7
0 2
8 17

Sample Output

5 10 18

Sample Input

2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000

Sample Output

2 1500000000000000000

【Problem Description】

  n  ， i     i       a[i],   i   j  ，  a[i]+j
q   ，     n ，[l,r]             。

    ：
7~7： 8,10,11,12,16.

Fret 0 1 2 3 4 5 6 7 … s 1 : 3 4 5 6 7 8 9 10 … s 2 : 1 2 3 4 5 6 7 8 … s 3 : 4 5 6 7 8 9 10 11 … s 4 : 1 2 3 4 5 6 7 8 … s 5 : 5 6 7 8 9 10 11 12 … s 6 : 9 10 11 12 13 14 15 16 …\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} Frets1​:s2​:s3​:s4​:s5​:s6​:​0314159​14252610​25363711​36474812​47585913​586961014​6971071115​71081181216​…………………​
【Solution】

   n        ，        ：1 1 3 4 5 9

     ，    [l,r]     [0,r-l+1]    
   r  ：r=r-l+1
                r     ：
         ：
          1  ，          ，         ，       ，   
             
          1  ，          2，             1 2    。
          3  ，          1，             3  。
    ……
    ……
            i           a[i+1]-a[i], n          r-a[n]
                  

         [0,r]   ，         ？
     i      min(r,a[i+1]-a[i])，  ：          min(r,a[i+1]-a[i])

     q   ，     n ，      O(n*q)    

      ：    [1,n-1]        0 2 1 1 4，     ：0 1 1 2 4
            [0,r]，         r     t       。
    [1,t]       r ，[t+1,n-1]    r 
          sum[1,t]+((n-1)-t)*r+       r,    =sum[1,t]+(n-t)*r
     t           ，sum           。

【Code】

/*
 * @Author: Simon 
 * @Date: 2019-04-06 22:35:16 
 * @Last Modified by: Simon
 * @Last Modified time: 2019-04-06 22:40:29
 */
#include
using namespace std;
typedef int Int;
#define int long long
#define INF 0x3f3f3f3f
#define maxn 100005
int a[maxn],b[maxn],s[maxn];
Int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=2;i<=n;i++){
        b[i-1]=a[i]-a[i-1]; //          
    }
    sort(b+1,b+n); //      
    for(int i=1;i<n;i++) s[i]=s[i-1]+b[i]; //      
    int q;cin>>q;
    while(q--){
        int x,y;cin>>x>>y;y=y-x+1;
        int t=upper_bound(b+1,b+n,y)-b-1; //       y     t
        cout<<s[t]+(n-t)*y<<' ';
    }
    cout<<endl;
    cin.get(),cin.get();
    return 0;
}