D. Frets On Fire(思维,排序)

$先按照s_i从小到大排序$

$设第一个区间是[s_1+l,s_1+r],那么对答案贡献是r-l+1$

$考虑第二个区间[s_2+l,s_2+r],那么对答案是多少?$

$显然当s_2+l>s1+r时,对答案贡献是r-l+1,也就是和上一个区间不重叠$

$否则重叠,对答案贡献是s2-s1$

$所以每个区间对答案的贡献是min(r-l+1,s_i-s_{i-1})$

$但是,这样的复杂度还不够优秀,每次询问都要O(n)的时间来求$

$所以我们把所有的s_i-s_{i-1}求出来,记作数组d[i]$

$那么显然,如果d_i>=r-l+1,那么贡献r-l+1可以取满$

$否则,区间有部分重复了,贡献为d_i$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
ll s[maxn],d[maxn],pre[maxn],n;
ll find(ll x)
{
	ll l=1,r=n,mid;
	while(r>l)
	{
		mid=l+r>>1;
		if(d[mid]>=x)	r=mid;
		else	l=mid+1;
	}
	return r;
}
int main()
{
	cin >> n;
	for(int i=1; i<=n ;i++)	cin >> s[i];
	sort(s+1,s+1+n);
	for(int i=2;i<=n;i++)	d[i-1]=s[i]-s[i-1];
	sort(d+1,d+n);
	cout<<endl;
	for(int i=1;i<n;i++)	pre[i]=pre[i-1]+d[i];
	int q;cin>>q;
	for(int i=1;i<=q;i++)
	{
		ll l,r;
		cin>>l>>r;
		ll len=r-l+1;
		ll num=find(len);//num后的可以打满,之前的要减去d[i]
		ll ans=len*(n-num+1)+pre[num-1];
		cout<<ans<<" "; 
	}
}