CF-1119 D. Frets On Fire(排序，二分)

题目链接
题意：给定n个数。k次查询， 给定一个区间 [li, ri]， 对n个数分别从li 加到 ri ,统计过程中出现的不同数的个数。
思路：对于区间 [li, ri] 以及 a[i] 和 a[i-1] , 如果a[i]-a[i-1] > ri - li + 1 那么这里就会有 ri - li + 1 个不同的数。
由此，应当先将数组排序。然后就这样统计累加答案。
提交， 超时。
优化：排序后，相邻两个数之间的差大于区间长度，ans += 区间长度， 否则就 += 相邻两数之差。所以可以将两数之差保存，并排序，这样的话，每次查询的时候，就可以直接二分区间长度，对于前面的就直接将差相加（可以弄个前缀和数组），后面的就是 剩余个数*区间长度。

#include <bits/stdc++.h>
const int maxn = 100005;
using namespace std;
typedef long long ll;
ll s[maxn], cha[maxn], pre[maxn];

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        cin>>s[i];
    sort(s, s+n);
    for(int i=1; i<n; i++)
        if(s[i] > s[i-1])
            cha[m++] = s[i] - s[i-1];
    sort(cha, cha+m);
    pre[0] = cha[0];
    for(int i=1; i<m; i++)
        pre[i] = pre[i-1] + cha[i];
    int k;
    scanf("%d", &k);
    while(k--){
        ll l, r, len;
        cin>>l>>r;
        len = r - l +1;
        int t = upper_bound(cha, cha+m, len) - cha;
        ll ans = pre[t-1] + len * (m-t+1);
        cout<<ans<<endl;
    }
    return 0;
}