D. Frets On Fire

http://codeforces.com/contest/1119/problem/D

题意：给si表示从si开一直到1e18；问一个区间内不同的数有多少个；

思路：记录si的差值以及排序后差值的前缀和，因为区间大于两个si差值后不同的数就是差值，所以二分找到差值小于等于区间长度的，大于的不同个数就是区间长度；

#include<algorithm>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<ctime>
#include<map>
#include<stack>
#include<string>
#include<ctime>
using namespace std;

#define sfi(i) scanf("%d",&i)
#define pri(i) printf("%d\n",i)
#define sff(i) scanf("%lf",&i)
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define eps 1e-14
#define PI acos(-1)
#define lowbit(x) ((x)&(-x))
#define zero(x) (((x)>0?(x):-(x))<eps)
#define fl() printf("flag\n")
#define MOD(x) ((x%mod)+mod)%mod
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll gcd(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
const int maxn=3e5+9;
const int mod=1000000007;

inline ll read()
{
    ll f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

ll a[maxn],sum[maxn],cha[maxn],ch[maxn];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);

    int cnt=1;
    for(int i=1;i<n;i++)
    {
        ch[cnt++]=a[i+1]-a[i];
    }
    sort(ch+1,ch+cnt);

    int c=1;
    for(int i=1;i<cnt;i++)
    {
        if(ch[i])
        {
            cha[c++]=ch[i];
        }
    }

    //for(int i=1;i<c;i++) cout<<cha[i]<<" ";

    int cntt=2;
    sum[1]=cha[1];
    for(int i=2;i<c;i++)
    {
        sum[cntt]=sum[cntt-1]+cha[i];
        cntt++;
    }
    cha[c]=9e18;
    sort(sum+1,sum+cntt);
    //for(int i=1;i<cntt;i++) cout<<sum[i]<<" ";
    int q;
    cin>>q;
    while(q--)
    {
        ll l=0;
        ll r=0;
        cin>>l>>r;
        ll len=r-l+1;
        int pos=upper_bound(cha+1,cha+c+1,len)-cha;
        pos--;
        //cout<<pos<<" "<<sum[pos]<<endl;
        cout<<sum[pos]+len*(c-pos)<<endl;
    }
    return 0;
}