CF1278D

题目大意是给你5e5条线段，规定相交的线段可以让他们彼此的编号之间连出一条边。注意线段互相包含不算相交，且没有重复的端点，端点都是从1~2n,问你最后练出的图是不是一棵树
根据树的定义我们知道树的边数一定是n-1的，那么我们可以记录一下边数如果不是n-1那么就是NO否则我们再遍历一下图看看是不是可以组成一颗树
这里CF官方题解给了一种叫做sweep line approach的方法可以nlogn判断具体哪两个线段相交
首先，我们把线段的左端点右端点拆分，变成{v,id}v代表值id代表这是输入顺序的第几个例如1 3线段就要拆分成1 1 和 3 1
然后，我们把拆分的线段加入一个vector中再按照第一个值排序从小到大
接着，我们开一个set来记录vector内的元素
算法开始，我们最外层枚举vector内的元素，首先判断当前set内是否有这个元素如果有就删除继续走。因为如果有的话这都是右端点了直接删除可以避免重复计数
否则的话我们就遍历set看看里面有多少值是小于当前的节点编号的右端点值的小于就说明这俩一定相交那么我们就记录上就行了
最后把这个右端点再放入set中即可

for(int i=0;i<v.size();i++) //sweep line approach 
{
	if(cnt>=n) //判断如果边数多了就break 
	break;
	if(st.count(v[i])) //如果存在这个右端点了就删除 
	st.erase(v[i]);
	else
	{
		int r=a[v[i].second].second; //找到当前左端点的右端点 
		for(auto it=st.begin();it!=st.end();it++) //遍历set 
		{
			if(it->first>r)//因为set按照第一个元素排序的所以我们如果有大于的就一定后面都大于不满足当前题目的要求 
			break;
			G[v[i].second].push_back(it->second); //vector存图 
			G[it->second].push_back(v[i].second);
			cnt++;
			if(cnt>=n) //继续判断 
			break;	
		}
		st.insert(make_pair(r,v[i].second)); //放入这个右端点			
	}
}
//这里我们可以适用于其他的题目这个对于判断线段相交确实好用

然后我们dfs一遍看看是不是树就行了

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
pair<int,int> a[N];
bool mk[N];
vector<int> G[N];
void dfs(int p,int fa)
{
	mk[p]=1;
	for(int i=0;i<G[p].size();i++)
	if(!mk[G[p][i]])
	dfs(G[p][i],p);
}
int main()
{
	ios::sync_with_stdio(0);
	int n,cnt=0,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i].first>>a[i].second;
	vector<pair<int,int> > v;
	for(int i=1;i<=n;i++)
	{
		v.push_back(make_pair(a[i].first,i));
		v.push_back(make_pair(a[i].second,i));
	}
	sort(v.begin(),v.end());
	set<pair<int,int> > st;
	for(int i=0;i<v.size();i++)
	{
		if(cnt>=n)
		break;
		if(st.count(v[i]))
		st.erase(v[i]);
		else
		{
			int r=a[v[i].second].second;
			for(auto it=st.begin();it!=st.end();it++)
			{
				if(it->first>r)
				break;
				G[v[i].second].push_back(it->second);
				G[it->second].push_back(v[i].second);
				cnt++;
				if(cnt>=n)
				break;	
			}
			st.insert(make_pair(r,v[i].second));			
		}
	}
	dfs(1,1);
	for(int i=1;i<=n;i++)
	ans+=mk[i];
	if(cnt==n-1&&ans==n)
	cout<<"YES";
	else
	cout<<"NO";
}