codeforces D. Frets On Fire

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

 

题意： 

         还是得要认真读题啊，比赛时看这题目，做的心情都没有，后来认真仔细的读一下，还是挺好理解的。就是每个音符长都是1e18+1，给你n个音符的开头，比如一个音符的开头是3，那么它就是3，4，5，6.。。。。。。

然后给你q个问题，每次询问区间L,R中有多少个不同的音阶，这个区间不理解的看一下题目中的图，图的上方标出l区间的序号（0，1，2，4。。。。）

 

思路：

        如果只有一个音符，那么就有（R-L+1）个不同的音阶，而如果有两个音符的话，有多少呢。很显然，如果他们的开头相同，那么这两个音符就是相同的，而如果他们的开头不同的话，那么，当他们的开头的差不超过区间的的长度时就会有重复的部分，否则就没有重复的部分。

可以这样理解，我们以开头最小的一个为一个基础，那么这个有了（R-L+1）个，第二个音符在第一个音符的基础上多了多少个不同的音阶呢？很显然如果设一个开头是a1，第二个是a2，那么就多了min（a2-a1，R-L+1）；

于是当有n个音符时，我们可以这样考虑，首先把开头从小到大排序，并且去重，之后计算两两之间的差b[i],再把b从小到大排序，计算他们的前缀和sum[i]，之后对于每一次询问，我们，以最小的一个开头为基础，之后在b中二分查找第一个大于区间长的值，分别计算出结果加上即可。

具体请参看代码：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
typedef pair<int, int> p;
const int maxn = 1000*100  + 10;
const int mod = 1e9 + 7;
int n, m;
ll a[maxn],b[maxn],sum[maxn];
vector<ll>v;

int main() {

	ios::sync_with_stdio(false);
	cin >> n ;
	for (int i = 1; i <= n; i++)cin>>a[i];
	sort(a + 1, a + 1 + n);
	int cnt = 1;      //计数去重后的个数+1
	for (int i = 2; i <= n; i++) {
		if (a[i] == a[i - 1])continue; //去重
		b[cnt] = a[i] - a[i - 1];		//计算差值
		cnt++;
	}
	sort(b+1,b+cnt);
	sum[0] = 0;
	for(int i=1;i<cnt;i++)
		sum[i] = sum[i - 1] + b[i];    //计算前缀和
	
	cin >> m;
	ll L, R;
	while (m--) {
		cin >> L >> R;
		ll ans = 0;
		ans += (R-L+1);    //以最小的一个为基础先加上区间长
		ll k = upper_bound(b+1,b+cnt,R-L)-b; //查找第一个比区间长大的第一个数的位置
		ans += sum[k-1];			//前面的之间加上前缀和即可
		ans += (R-L+1)*(cnt - k);    //后面的因为大于区间长，但对于每一个音符来说，最多只有（R-L+1）个不同的音阶
		cout << ans <<' ';
	}

	return 0;
}