自动搬运

查看原文

来自洛谷，原作者为

	Light_az florr.io 同名 || 莱特阿哲

搬运于2025-08-24 22:45:57，当前版本为作者最后更新于2023-04-01 17:06:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

模拟大法好！

今年省选赛时看了旁边神仙一眼，第一题用了 $300$ 多行代码写了个线段树 ，赛后发现还有使用并查集和树状数组的人，但是个人认为此题没有这么麻烦，我们直接采用模拟的方式来完成这一题。

简化题意

由于原题面有点复杂，因此我稍微化简题意：给定 $m$ 条线段，覆盖点 $x$ 的线段我们定义为该线段合法，与合法的线段有任何重合的线段也合法（包括端点重合），求合法线段的端点。

解法

首先通过分析样例我们可以得到这样一张图：

（图丑请见谅）

看完这张图片也许你会有一个疑问，为什么 $5$ 号点是合法线段端点，却不是正确答案呢？再次阅读题目后，我们知道：火车无法掉头，只能朝着一个方向运行，也就是说，火车是往 $7$ 号点的方向开去的，不能掉头或者瞬间停下到 $5$ 号点。由此我们可以得出结论：

• 如果合法线段在点 $x$ 的右侧，那么答案编号一定是它的右端点（因为方向是往右的）

• 如果合法线段在点 $x$ 的左侧，那么答案编号一定是它的左端点（因为方向是往左的）

• 如果合法线段覆盖了点 $x$，那么答案编号一定是它的左，右端点（因为火车从中间出发，方向可以往左也可以往右）

在处理完之后，我们就要把步骤退回来求合法线段了，我们假设你正在玩搭桥游戏，有很多木板可以搭桥，那么你搭桥的形状一定是这样的：

由上图我们发现每一块木板的端点一定是在上一块木板上，那么我们可以用这个思路寻找合法线段，首先定义 $l,r$ 分别是合法线段的最大左端点和最大右端点，如果说一个线段的左端点或者右端点处于这个区间内（即与合法线段重合），那么这个线段也合法，于是我们可以使用两个循环，分别求出 $l,r$ 的最值，即：

F1(i,1,n) if(a[i].l>=mini&&a[i].l<=maxi) maxi=max(maxi,a[i].r);//线段左端点位于合法区间内，该线段合法，更新右端点的最值
F2(i,n,1) if(a[i].r>=mini&&a[i].r<=maxi) mini=min(mini,a[i].l);//同上，但是需要倒推，因为线段排序后的上升性，后面有讲

（为了方便理解，将 $l,r$ 换成了 $mini,maxi$ ）

当然，当某一条线段覆盖了 $x$ 号点时，根据前面的定义那么该线段是合法的，左右端点都是答案，所以也要更新最两端的大值，即：

if(a[i].l<=x&&x<=a[i].r){//覆盖 x 号点
		mini=min(mini,a[i].l);//取最值
		maxi=max(maxi,a[i].r);
		v[a[i].l]=v[a[i].r]=1;//标记合法
} 

在完成以上处理之后，如果一条线段没有完全覆盖在 $l,r$ 之间时，这一条线段一定不合法。

最后根据上面搭桥的那一张图片，我们发现从左到右的每一块木板的左端点和右端点一定是不下降的，首先来看一张图：

我们发现第 $3$ 条线段应该是合法的，但是由于我们遍历线段的顺序是按照编号的，所以它的遍历顺序应该是左，右，中。此时第 $3$ 条线段就不合法了，因为它与唯一的合法线段也就是第 $1$ 条线段没有重合部分。

然后我们对线段进行排序后，就得到了下面这张图片：

此时第 $3$ 条线段就是合法的，因为它与第 $2$ 条线段有重合部分，而第 $2$ 条线段又与合法线段 $1$ 有重合部分，由此我们可以得出结论：线段要采取排序，从而保证端点的不下降性

最后输出时我们套用上第一步的样例结论做最后的特判即可（还需要标记数组给答案打标记，说明此点是合法线段的端点），后面是代码部分：

#include<bits/stdc++.h>
#define ll long long
#define F1(i,j,n) for(int i=j;i<=n;i++)
#define F2(i,j,n) for(int i=j;i>=n;i--)
using namespace std;
const int N=1e6+10,NN=1e4+10;
ll n,m,k,x,y,u,w,cnt=0,ans=0,t=0,l,r,len,T;
ll mini=INT_MAX,maxi=0,Mod;
bool v[N];
struct Node{
	ll l,r; 
}a[N];
bool cmp(Node a,Node b){
	if(a.l==b.l) return a.r<b.r;
	return a.l<b.l;
}
int main(){
	cin>>m>>n>>x; 
	F1(i,1,n){
		cin>>a[i].l>>a[i].r;//双端编号
		if(a[i].l<=x&&x<=a[i].r){//覆盖x号点，即合法区间 
			mini=min(mini,a[i].l);//更新合法端点最值 
			maxi=max(maxi,a[i].r);
			v[a[i].l]=v[a[i].r]=1;//线段两端标记为答案 
		} 
	}
	sort(a+1,a+1+n,cmp);//排序 
	F1(i,1,n) if(a[i].l>=mini&&a[i].l<=maxi) maxi=max(maxi,a[i].r);//左端与合法线段有重合部分，更新最大值
	F2(i,n,1) if(a[i].r>=mini&&a[i].r<=maxi) mini=min(mini,a[i].l);//右端与合法线段有重合部分，更新最大值
	F1(i,1,n){
		if(a[i].l<mini||a[i].r>maxi) continue;//不是合法线段 
		if(a[i].r<x) v[a[i].l]=1;//由结论得，该合法线段在x号点左边时，左端点是答案 
		else v[a[i].r]=1;//同上 
	}
	F1(i,1,m) if(v[i]&&i!=x) cout<<i<<" ";//此编号标记为答案且不是起点 
	return 0;
}