P12502 「ROI 2025 Day1」天狼星的换班 「线段覆盖问题」

题目传送门

线段覆盖问题，数据结构优化 DP。

题意

是否能从给定的 \(k\) 条线段 \((l,m,r)\) 中按照某种顺序地挑出任意个线段覆盖区间 \([1,n]\)，并满足如下条件：

后挑出的线段的 \(m\) 不能落在已挑出的线段上。

\(1 \leq n,k \leq 5 \times 10^5\)，\(1 \leq l \leq m \leq r \leq n\)。

题解

这是一个线段覆盖问题，我们像搭桥一样，先从 \(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\) 是否被覆盖即可。

于是我们就做完啦！

Tip：这里的 \(\text{set}\) 实际上是存储了有用的 \(\text{DP}\) 决策点，并且和树状数组一起，对朴素的 \(\text{DP}\) 进行了优化，只不过题解里跳过了优化前的过程。

代码

#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;
}