这个题真的难了我一天了，这种方法一开始没想出来，后来看了题解后明白了大致思路开始自己做但是！！！但是自己实现的时候老是一些细节出错！！！，调bug调了得有一个小时，蠢死了，这道题我一定要好好总结，总结为什么会卡壳，这要是比赛的签到题的话我得哭死！！！！！

 

#include
     
      using namespace std;const int maxn=1e5+10;unsigned long long a[maxn];unsigned long long c[maxn];unsigned long long sum[maxn];set
      
        s;int main(){    int n;    cin>>n;    for(int i=1; i<=n; i++)    {        unsigned long long t;        cin>>t;        s.insert(t);    }    int cnt=0;    for(auto i:s)        a[++cnt]=i;    for(int i=1; i<=cnt-1; i++)        c[i]=a[i+1]-a[i];    cnt--;    sort(c+1,c+1+cnt);    for(int i=1; i<=cnt; i++)        sum[i]=sum[i-1]+c[i];    int q;    cin>>q;    while(q--)    {        unsigned long long l,r;        cin>>l>>r;        unsigned long long t=r-l;        unsigned long long pos;        unsigned long long ans=0;        pos=upper_bound(c+1,c+1+cnt,t)-c;        ans+=1+t;        ans+=(sum[pos-1]);        ans+=(cnt-pos+1)*(t+1);        cout<
       
        <
       
      
     

读题之后我的最直接的思路是把这n个数，去重排序，然后是比较两两之间的长度与r-l的区间长度的关系然后一直累加出答案。如下超时代码。

我应该要注意到这两两之间的差值也是可以排序的，排完序之后只要在小于等于r-l的区间长度的都是我下面if语句的第一条，大于r-l区间长度的都是else语句的内容，这个判断可以二分来实现，同时对于小于等于区间长度的可以用预先求出前缀和来快速计算。

 

#include
     
      using namespace std;set
      
        s;const int maxn=1e5+10;unsigned long long a[maxn];unsigned long long b[maxn];int main(){    int n;    cin>>n;    for(int i=1; i<=n; i++)        cin>>a[i];    int q;    cin>>q;    while(q--)    {        unsigned long long l,r;        s.clear();        memset(b,0,sizeof(b));        cin>>l>>r;        for(int i=1; i<=n; i++)            s.insert(a[i]+l);        unsigned long long t=r-l;        int cnt=0;        for(auto i:s)            b[++cnt]=i;        unsigned long long ans=0;        for(int i=1; i<=cnt-1; i++)        {            if((b[i]+t)>=b[i+1])                ans+=b[i+1]-b[i];            else                ans+=t+1;        }        ans+=t+1;        printf("%lld\n",ans);    }}