线段树

#include<bits/stdc++.h>
using namespace std;
int n,m,x;
struct w{
	int l,r;
}s[1000011];
int cnt,ans[2000011];//ans[]:记录所有能到达的ans
int t[1600002],laz[1600002];//t[]:线段树  laz[]:延迟下传 
void down(int now)
{
	//下传laz数组 
	t[now*2]=max(t[now*2],laz[now]);
	t[now*2+1]=max(t[now*2+1],laz[now]);
	laz[now*2]=max(laz[now],laz[now*2]);
	laz[now*2+1]=max(laz[now],laz[now*2+1]);
	laz[now]=0;
	return;
}
void down2(int now)
{
	//下传laz数组
	t[now*2]=min(t[now*2],laz[now]);
	t[now*2+1]=min(t[now*2+1],laz[now]);
	laz[now*2]=min(laz[now],laz[now*2]);
	laz[now*2+1]=min(laz[now],laz[now*2+1]);
	laz[now]=1061109567;
	return;
}
void update(int now,int l,int r,int x,int y,int k)
{
	if(y<l||x>r)
		return;
	if(l>=x&&r<=y)
	{
		//当前now能到达的最大点 
		t[now]=max(t[now],k);
		laz[now]=max(laz[now],k);
		return;
	}
	down(now);
	int mid=(l+r)/2;
	update(now*2,l,mid,x,y,k);
	update(now*2+1,mid+1,r,x,y,k);
	//维护线段树最大值 
	t[now]=max(t[now*2],t[now*2+1]);
	return;
}
void update2(int now,int l,int r,int x,int y,int k)
{
	if(y<l||x>r)
		return;
	if(l>=x&&r<=y)
	{
		//当前now能到达的最小点 
		t[now]=min(t[now],k);
		laz[now]=min(laz[now],k);
		return;
	}
	down2(now);
	int mid=(l+r)/2;
	update2(now*2,l,mid,x,y,k);
	update2(now*2+1,mid+1,r,x,y,k);
	//维护线段树最小值 
	t[now]=min(t[now*2],t[now*2+1]);
	return;
}
int query(int now,int l,int r,int x,int y)
{
	//查询区间最大值 
	if(y<l||x>r)
		return 0;
	if(x<=l&&y>=r)
		return t[now];
	down(now);
	int mid=(l+r)/2;
	return max(query(now*2,l,mid,x,y),query(now*2+1,mid+1,r,x,y));
}
int query2(int now,int l,int r,int x,int y)
{
	//查询区间最小值
	if(y<l||x>r)
		return 1061109567;
	if(x<=l&&y>=r)
		return t[now];
	down2(now);
	int mid=(l+r)/2;
	return min(query2(now*2,l,mid,x,y),query2(now*2+1,mid+1,r,x,y));
}
int main()
{
//	freopen("station.in","r",stdin);
//	freopen("station.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>x;
	//建最大值线段树 
	for(int i=1;i<=m;i++)
	{
		cin>>s[i].l>>s[i].r;
		//线段树更新l~r最大走到r 
		update(1,1,n,s[i].l,s[i].r,s[i].r);
	}
	//从x开始向后跳 
	int maxto=x;
	while(maxto<=n)
	{
		//向后走到maxto能达到的最后的点 
		int nowmax=query(1,1,n,maxto,maxto);
		if(nowmax<=maxto)
			break;
		maxto=nowmax;
	}
	//若能到达maxto 则x~maxto之间所有的终点r都能到达 
	for(int i=1;i<=m;i++)
		if(s[i].r>x&&s[i].r<=maxto)
			ans[++cnt]=s[i].r;
	//重建最小值线段树 
	memset(t,0x3f,sizeof(t));
	memset(laz,0x3f,sizeof(laz));
	for(int i=1;i<=m;i++)
		update2(1,1,n,s[i].l,s[i].r,s[i].l);
		//线段树更新l~r最小走到l 
	maxto=x;//从x开始向前跳 
	while(maxto>=1)
	{
		//向前走到maxto能达到的最前的点 
		int nowmax=query2(1,1,n,maxto,maxto);
		if(nowmax>=maxto)
			break;
		maxto=nowmax;
	}
	//若能到达maxto 则maxto~x之间所有的终点l都能到达 
	for(int i=1;i<=m;i++)
		if(s[i].l>=maxto&&s[i].l<x)
			ans[++cnt]=s[i].l;
	sort(ans+1,ans+cnt+1);//排序 
	for(int i=1;i<=cnt;i++)
		if(ans[i]!=ans[i-1])//去重 
			cout<<ans[i]<<" ";
	return 0;
}