题目链接:codeforces 1119D
题目思路:
数据这么大一定是找规律……求区间里数的个数,与顺序无关,不妨先排个序。不难发现当 a [ i ] + r > = a [ i + 1 ] − l a[i]+r >= a[i+1]-l a[i]+r>=a[i+1]−l 时,就会又重叠的部分。于是想到差分,并对差分数组排序,用前缀和维护前面有重叠的部分。二分查找有重叠和未重叠的分界,即第一个大于等于 len 的下标。
参考代码:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N], d[N], pre[N];
int main() {
int n, q;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a+1, a+1+n);
n = unique(a+1, a+1+n) - a - 1;
for (int i = 1; i <= n-1; i++) {
d[i] = a[i+1] - a[i];
}
sort(d+1, d+n);
for (int i = 1; i <= n-1; i++) {
pre[i] = pre[i-1] + d[i];
}
cin >> q;
while (q--) {
ll l, r, x, len;
cin >> l >> r;
len = r - l + 1;
x = lower_bound(d+1, d+n) - d - 1;
cout << pre[x] + (n - x) * len << ' ';
}
return 0;
}