Codeforces 689E Mike and Geometry Problem

链接

传送门

题意

给出$n$个区间,问所有选择$k$个不同区间的方法下它们相交区间的长度和。

思路

离散化之后用扫描线维护有多少个区间包含当前子区间,然后当前区间的贡献为${num \choose k} \cdot 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
const int maxn = 200010;
int l[maxn], r[maxn];
int Hash[maxn << 1], sum[maxn << 1];
LL inv[maxn], fac[maxn], invfac[maxn];
LL C(int n, int k) {
return fac[n] * invfac[k] % mod * invfac[n - k] % mod;
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
int num = 0;
inv[1] = fac[1] = fac[0] = invfac[1] = invfac[0] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
fac[i] = fac[i - 1] * i % mod;
invfac[i] = invfac[i - 1] * inv[i] % mod;
}
for (int i = 0; i < n; ++i) {
scanf("%d%d", &l[i], &r[i]);
Hash[num++] = l[i];
Hash[num++] = r[i] + 1;
}
sort(Hash , Hash + num);
num = int(unique(Hash, Hash + num) - Hash);
for (int i = 0; i < n; ++i) {
++sum[int(lower_bound(Hash, Hash + num, l[i]) - Hash)];
--sum[int(lower_bound(Hash, Hash + num, r[i] + 1) - Hash)];
}
int tmp = sum[0];
LL ans = 0;
for (int i = 1; i < num; ++i) {
if (tmp >= k) {
ans = (ans + C(tmp, k) * (Hash[i] - Hash[i - 1])) % mod;
}
tmp += sum[i];
}
printf("%lld\n", ans);
return 0;
}

支付宝扫码领红包