P12502 「ROI 2025 Day1」天狼星的换班 （线段覆盖问题）
A2ure_Sky
·
·
题解
题目大意
是否能从给定的 k 条线段 (l,m,r) 中按照某种顺序地挑出任意个线段覆盖区间 [1,n]，并满足如下条件：
后挑出的线段的 m 不能落在已挑出的线段上。
数据范围
# 题解
这是一个线段覆盖问题，我们像搭桥一样，先从 $1$ 开始拼接线段，最后拼到 $n$，因此按 $l$ 排序是合理的。
特别要考虑的是 $m$ 这个约束，我们首先看看怎样才是合法的拼接。
考虑两条线段 $X$ 和 $Y$，其中 $l_X \leq l_Y$。
首先能够拼接的必要条件是 $X$ 和 $Y$ 相交或相邻，即 $r_X \geq l_Y - 1$。
注意到如果两个线段的 $m$ 都被对方的区间所覆盖的情况显然无法拼接，那么只有两种情况：
1. $m_Y$ 未被覆盖，此时可以先选 $X$ 再选 $Y$。
**示例图**：
```
---·-- X
----·-- Y
```
由图可知需满足： $r_X \in [l_Y - 1, m_Y - 1]$。
2. $m_X$ 未被覆盖，此时可以先选 $Y$ 再选 $X$。
**示例图**：
```
---·----- X
-·-- Y
```
由图可知需满足： $l_Y \in [m_X + 1, r_X + 1]$。
**上面两种情况满足其一即可拼接**。
---
于是我们就分析完了拼接的问题，现在问题就好办了。
按 $l$ 从小到大维护已经拼接出的若干个区间 $[1,r_X]$，考虑新引入的线段 $A$ 是否可以拼接上前面的区间，这里可以使用 **set** 维护 $x$。
注意我们并不关心拼接的是哪一个区间而只关心是否能拼上，因为拼接完的区间都是 $[1,r_A]$。
根据前面说的，只要满足两个条件中的一个就可以拼接：
- 对于前者，我们在 **set** 上二分出一个满足 $r_X \geq l_Y - 1$ 的最小的 $r_X$ 并判断是否 $\leq m_Y - 1$（为了方便可以整体加上一）。
- 对于后者，我们可以借助**树状数组**用**差分**的方式维护出区间 $[m_X + 1, r_X + 1]$，然后单点查询 $l_Y$ 是否被覆盖即可。
于是我们就做完啦！
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,k;
struct node{
int l,m,r;
bool operator < (const node &b) const{
return (l!=b.l)?(l<b.l):(r<b.r);
}
}a[N];
set<int> S;
int t[N];
void upd(int x,int y){for(;x<=n+2;x+=x&(-x)) t[x]+=y;}
int qry(int x){
int res=0;
for(;x;x-=x&(-x)) res+=t[x];
return res;
}
void solve(){
cin>>n>>k;
S.clear();
for(int i=1;i<=n+2;i++) t[i]=0;
for(int i=1;i<=k;i++) cin>>a[i].l>>a[i].m>>a[i].r;
sort(a+1,a+k+1);
int ans=0;
for(int i=1;i<=k;i++){
auto it=S.lower_bound(a[i].l);
if(it!=S.end()&&(*it)<=a[i].m||a[i].l==1||qry(a[i].l)){
ans=max(ans,a[i].r);
S.insert(a[i].r+1);
upd(a[i].m+1,1),upd(a[i].r+2,-1);//注意树状数组的值域
}
}
cout<< ( (ans==n) ? "YES\n" : "NO\n");
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T; cin>>T;
while(T--) solve();
return 0;
}