题解：P12502 「ROI 2025 Day1」天狼星的换班
2huk
·
·
题解
将所有区间按照右端点排序。设 $f_i$ 表示若只考虑前 $i$ 条线段，能否覆盖 $1 \sim r_i$。
一些简单的观察，最终选的线段子集中不存在一个完全包含另一个，也不存在三个线段有交。
对于一个线段子集，如果它能覆盖全局，我们考虑它们的覆盖顺序，使得每次染色时位置 $m$ 上仍为空。不难发现一个必要条件是，对于两个有交的线段 $[l_i,r_i],[l_j,r_j]$，假设 $l_j < l_i \le r_j < l_j$，那么 $m_i,m_j$ 不能同时在区间 $[l_i,r_j]$ 中。画画图发现这也是充分的，证明大概是，把有先后顺序要求的线段间建有向边，发现是 DAG，所以显然有解。
然后考虑转移。枚举上一个线段 $j<i$，需要满足 $r_j \ge l_i-1$。如果 $m_i,m_j$ 不同时在 $[l_i,r_j]$ 中就能转移。代码大概这样：
:::success[$\mathcal O(n^2)$]
```cpp
bool solve() {
cin >> n >> m;
for (int i = 1; i <= m; ++ i ) {
cin >> a[i].l >> a[i].m >> a[i].r;
}
sort(a + 1, a + m + 1, [&](Range x, Range y) {
return x.r < y.r;
});
for (int i = 1; i <= m; ++ i ) {
f[i] = a[i].l == 1;
for (int j = 1; j < i; ++ j )
if (a[j].r >= a[i].l - 1) {
int l = a[i].l, r = a[j].r;
f[i] |= f[j] && !(l <= a[i].m && a[i].m <= r && l <= a[j].m && a[j].m <= r);
}
if (f[i] && a[i].r == n) return 1;
}
return 0;
}
```
:::
分类讨论“$m_i,m_j$ 不同时在 $[l_i,r_j]$ 中”：
- $m_i$ 不在 $[l_i,r_j]$ 中：即 $m_i > r_j$。
- $m_j$ 不在 $[l_i,r_j]$ 中：即 $m_j < l_i$。
分别做这两种转移。因为 DP 是取或，所以无需考虑重复转移的问题。
- 第一种，要求是 $l_i-1 \le r_j < m_i$。前面做到 $j$ 时，如果 $f_j=1$，就在树状数组的 $r_j$ 处加一，然后求 $[l_i-1,m_i-1]$ 的区间和即可。
- 第二种，要求是 $m_j<l_i \le r_j+1$。前面做到 $j$ 时，如果 $f_j=1$，在另一个树状数组的区间 $[m_j+1,r_j+1]$ 处做区间加一，然后求 $l_i$ 的单点值即可。
:::success[$\mathcal O(n \log n)$]
```cpp
bool solve() {
cin >> n >> m;
for (int i = 1; i <= m; ++ i ) {
cin >> a[i].l >> a[i].m >> a[i].r;
}
sort(a + 1, a + m + 1, [&](Range x, Range y) {
return x.r < y.r;
});
T.clear(), P.clear(); // T,P 是两个树状数组
for (int i = 1; i <= m; ++ i ) {
f[i] = a[i].l == 1 ||
T.query(a[i].m - 1) - T.query(a[i].l - 2) > 0 ||
!!P.query(a[i].l);
if (f[i]) {
T.modify(a[i].r, 1);
int l = a[i].m + 1, r = a[i].r + 1;
P.modify(l, 1), P.modify(r + 1, -1);
}
if (f[i] && a[i].r == n) return 1;
}
return 0;
}
```
:::
考虑怎么去掉这两个树状数组。
- 第一种：注意到 $r_j$ 是单调增的，因此可以直接用前缀和代替树状数组。
- 第二种：使用[白雪皑皑](https://www.luogu.com.cn/problem/P2391)这个题的 trick，用并查集找到空的位置赋值，复杂度均摊 $\mathcal O(1)$。
当然了，还要把 sort 替换成桶排序。
:::success[$\mathcal O(n)$]
```cpp
bool solve() {
cin >> n >> m;
for (int i = 1; i <= m; ++ i ) {
cin >> a[i].l >> a[i].m >> a[i].r;
}
sort(a + 1, a + m + 1, [&](Node p, Node q) {
return p.r < q.r;
});
for (int i = 1; i <= n + 1; ++ i ) st[i] = s[i] = 0, p[i] = i;
int lst = 0;
for (int i = 1; i <= m; ++ i ) {
for (int k = lst + 1; k <= a[i].r; ++ k ) s[k] = s[k - 1];
lst = a[i].r;
f[i] = a[i].l == 1 || st[a[i].l] || s[a[i].m - 1] - (a[i].l - 2 > 0 ? s[a[i].l - 2] : 0);
if (f[i]) {
s[a[i].r] ++ ;
int l = a[i].m + 1, r = min(n, a[i].r + 1);
if (l <= r) {
l = p[l];
while (l <= r) st[l] = 1, l = p[l] = fifa(l + 1);
}
}
if (f[i] && a[i].r == n) return 1;
}
return 0;
}
```
:::