自动搬运

查看原文

来自洛谷，原作者为

	A2ure_Sky El Psy Kongroo

搬运于2025-08-24 23:16:02，当前版本为作者最后更新于2025-05-02 16:59:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

是否能从给定的 $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$ 是否被覆盖即可。

于是我们就做完啦！

代码

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