CodeForces 1119D（差分+前缀和+二分）

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 #define ll long long
 5 using namespace std;
 6 
 7 ll q[100100]={0},p[100100]={0},pos[100100]={0};
 8 int main()
 9 {
10     int n;
11     scanf("%d",&n);
12     for(int i=0;i<n;i++){
13         scanf("%lld",&q[i]);
14     }
15     sort(q,q+n);
16     for(int i=0;i<n-1;i++){
17         p[i]=q[i+1]-q[i];         //求出数组里i和i-1的差值存起来
18     }
19     sort(p,p+n-1);
20     for(int i=0;i<n;i++){
21         pos[i+1]=pos[i]+p[i];     //求差值的前缀和
22     }
23     ll m,a,b;
24     scanf("%lld",&m);
25     while(m--){
26         scanf("%lld%lld",&a,&b);
27         ll s=b-a+1;
28         ll sum=s+q[n-1]-q[0];                            //没加时的最小值到加了的最大值之间的个数
29         ll mid=upper_bound(p,p+n-1,s)-p;                //lower_bound 和 upper_bound 都可emmmmmm...不知道为啥(毕竟我菜)
30         sum=sum-(pos[n-1]-pos[mid])+(n-1-mid)*s;         //lower返回大于或等于s的第一个值的下标  upper 大于
31        
32         //（pos[n-1]-pos[mid]）后边差值大于s的差值和
33         //(n-1-mid)*s后边差值大于s的加上了s （前边小于或等于s的直接加差值）
34         
35         printf("%lld\n",sum);
36     }
37     return 0;
38 }