CF 1119D Frets On Fire

题目链接：http://codeforces.com/problemset/problem/1119/D

解题思路：

首先我们先将询问简化，询问的这个区间在哪其实是没有意义的，我们只需知道区间的长度w就可以了

如果两个数的差值小于w，下一行对于上一行的贡献是这个差值

否则就是w

对原先n个数排好序去重之后，就可以直接按照这个结论来做了。

对排序去重的数搞一个差分数组，对差分数组再排序，对排完序的差分数组再搞一个前缀和数组

每次二分查找差分数组中w的位置，小于等于w的直接 O（1）前缀和，大于的都是w

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 1e5+5;

ll a[N];
ll chafen[N],pre[N];

int main()
{
    int n;
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;i++) scanf("%I64d",a+i);
        sort(a+1,a+n+1);
        int cnt = unique(a+1,a+1+n) - a;///unique返回重复元素的首地址，也就是元素个数+1
/*
        printf("a:\n");
        for (int i=1;i<cnt;i++) printf("%I64d ",a[i]);
*/
        ///a  1~cnt-1
        for (int i=2;i<cnt;i++)
            chafen[i-1] = a[i]-a[i-1];
/*
        printf("\nchafen:\n");
        for (int i=1;i<cnt-1;i++) printf("%I64d ",chafen[i]);
*/
        ///chafen 1~cnt-2
        sort(chafen+1,chafen+cnt-1);
        for (int i=1;i<cnt-1;i++){
            pre[i] = pre[i-1] + chafen[i];
        }///pre 1~cnt-2
/*
        printf("\npre:\n");
        for (int i=1;i<cnt-1;i++) printf("%I64d ",pre[i]);puts("");
*/
        int q;
        ll l,r,w;
        scanf("%d",&q);
        bool flag = true;
        while (q--){
            scanf("%I64d %I64d",&l,&r);
            w = r-l+1;
            int pos = lower_bound(chafen+1,chafen+cnt-1,w) - chafen;
/*
            printf("pos=%d\n",pos);
*/
            ll ans = w + pre[pos-1];
            ans += (cnt-2-pos+1)*w;
            if (flag) flag = false;
            else printf(" ");
            printf("%I64d\n",ans);
        }
        printf("\n");
    }
    return 0;
}