魔音吉他

★问题描述

少年甲很喜欢音乐，有一天他来到了少年乙的村落。少年甲一曲高山流水，寻觅到了乙这位知音。然而，天下没有不散的宴席，少年甲要回村杀猪了，离别在即，少年乙拿出了自己珍藏多年的吉他，作为离别的礼物。就在少年甲欣喜之际，少年乙说，这把吉他变幻莫测，每次你拿起它的时候，它会有n根弦，每根弦可以演奏出10^18+1个音符，而这些个音符是连续的，取决于它每根弦的第一个音符（请看样例说明）。 此时，少年甲提出了一个疑问，如果给定一个区间l，r（包括端点），里面共有几种不同的音符呢？少年乙对此谙熟于心，但是他想考验一下你，于是将这个问题抛给了你。

★数据输入

第一行一个正整数n(1<=n<=100,000)，表示吉他有几根弦。 第二行共n个数x，即代表对应弦的第一个音符(0<=x<=10^18)。 第三行一个正整数q(1<=q<=100,000)，表示少年甲的询问次数。 接下来q行，每行两个数l，r(0<=l，r<=10^18+1)，表示少年甲想要询问的区间。

★数据输出

输出共q个数，表示对应q个询问的答案。即询问区间内有多少个不同的音符。以空格隔开。

★输入示例

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

★输出示例

5 10 18

★样例说明

列下标：0 1 2 3 4 5 …… 弦一：3 4 5 6 7 8 …… 弦二：1 2 3 4 5 6 …… 弦三：4 5 6 7 8 9 …… 弦四：1 2 3 4 5 6 …… 弦五：5 6 7 8 9 10 …… 弦六：9 10 11 12 13 14 ……

★Hint

（1）询问区间l，r即为样例说明中的列下标。 （2）所谓不同音符个数，即区间l，r内n行内不同的数字个数。 （3）由于l，r的范围巨大，请思考其与每行第一个数字的关系（即给出的第一个音符）。

代码（复杂度q*logn）

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+10;
const ull INF=1000000000000000001;
int n,q,m;
ull a[N],s[N];
unordered_set<ull> se;
int main()
{
    cin>>m;
    ull t;
    while(m--)
    {
        scanf("%llu",&t);
        if(!se.count(t)) a[++n]=t;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n-1;i++)  a[i]=a[i+1]-a[i];
    a[n]=INF;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    cin>>q;
    while(q--)
    {
        ull x,y;
        scanf("%llu%llu",&x,&y);
        x=y-x+1;
        int l=0,r=n;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(a[mid]<=x) l=mid;
            else r=mid-1;
        }
        cout<<s[l]+x*(n-l)<<' ';
    }
    return 0;
}