CF1119 D.Frets On Fire【二分】

题目链接：codeforeces 1119D

题解

数据这么大一定是找规律……

求区间里数的个数，与顺序无关，不妨先排个序。不难发现当 时，就会又重叠的部分。于是想到差分，并对差分数组排序，用前缀和维护前面有重叠的部分。二分查找有重叠和未重叠的分界，即第一个大于等于 len 的下标。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}