CF div2 D. Frets On Fire //思维

思维，预设区间全部能填满，找出不能填满的，所以要差值减来减去搞就行了

其实不用离散化，vector左闭右开增加我的劳动量。。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int max_n = 1e5+5;
vector<LL>v;
vector<LL>d;
vector<LL>PA;
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++){
       LL sc;scanf("%lld",&sc);v.push_back(sc);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    if(v.size()==1) n=1; //只有一个点
    for(int i=1;i<v.size();i++)d.push_back(v[i]-v[i-1]);
    sort(d.begin(),d.end());
    if(d.size())PA.push_back(d[0]);
    for(int i=1;i<d.size();i++) PA.push_back(d[i]+PA[i-1]);
    int q;scanf("%d",&q);
    while(q--){
        LL a,b;scanf("%lld%lld",&a,&b);
        if(n==1){printf("%lld\n",b+1-a);continue;} //只有一个点
        a=b-a+1;
        int id=upper_bound(d.begin(),d.end(),a)-d.begin();
        LL x;
        if(id==0)  x=PA[PA.size()-1]; //id==0
        else x=PA[PA.size()-1]-PA[id-1];
        x=x-(PA.size()-id)*(a);
        printf("%lld\n",v[v.size()-1]-v[0]+a-x);
    }

    return 0;
}