题目描述
https://www.luogu.com.cn/problem/P6146
简要题意：给定 $n$ 线段 $[l_i,r_i]$，保证不存在任何两条线段的左端点或右端点重合，定义若干条线段的复杂度为这些线段的并形成的连通块的个数，求这 $n$ 条线段的所有子集的复杂度之和
$n\le 10^5,1\le l_i\le r_i\le 2n$
Solution
我们考虑对于每一个连通块，我们认为是左端点最靠左的那个线段才有贡献
那么我们考虑单独计算每个线段的贡献
注意到线段 $i$ 如果能作出贡献，那么一定不存在线段 $j$，$l_j< l_i < r_j$
不妨设这样的线段 $j$ 的个数为 $s$，那么线段 $i$ 的贡献就是 $2^{n-s-1}$，注意到此题左端点不会重合
统计线段 $j$ 的数量可以用差分实现，时间复杂度 $O(n)$
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
| #include <iostream>
#include <cstdio>
#include <vector>
#define maxn 100010
#define maxm 200010
#define ll long long
using namespace std;
const int p = 1000000007;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1) {
if (n & 1) s = s * x % p;
x = x * x % p;
}
return s;
}
int n;
int l[maxn], r[maxn], d[maxm];
int ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i], ++d[l[i]], --d[r[i] + 1];
for (int i = 1; i <= 2 * n; ++i) d[i] += d[i - 1];
for (int i = 1; i <= n; ++i)
ans = (ans + pow_mod(2, n - d[l[i]])) % p;
cout << ans << "\n";
return 0;
}
|
我们考虑使用 $dp$ 来进行计数，同样我们还是考虑对于每一个连通块我们计算左端点最靠左的那个线段
为了避免后选的线段影响前面线段的连通块的个数，我们首先将线段按照左端点排序
令 $f[i]$ 表示前 $i$ 条线段的总贡献，我们加入第 $i$ 条线段时，首先能够使 $f[i-1]$ 翻倍
然后我们考虑第 $i$ 条线段自己的贡献，显然为 $2^{cnt}$，其中 $cnt$ 表示前 $i$ 条线段中与第 $i$ 条线段不相交的线段的个数
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define maxm 200010
#define ll long long
using namespace std;
const int p = 1000000007;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1) {
if (n & 1) s = s * x % p;
x = x * x % p;
}
return s;
}
int n;
pair<int, int> a[maxn];
int d[maxm], f[maxm];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second, ++d[a[i].second];
sort(a + 1, a + n + 1);
for (int i = 1; i <= 2 * n; ++i) d[i] += d[i - 1];
for (int i = 1; i <= n; ++i) {
f[i] = 2 * f[i - 1] % p;
f[i] = (f[i] + pow_mod(2, d[a[i].first - 1])) % p;
} cout << f[n] << "\n";
return 0;
}
|