P9166 [省选联考 2023] 火车站 题解
rmzls
·
·
题解
思路
废话不多说，我们先看题
我们只需要注意到两个点：
$2.$ 车只会一直沿着一条路线走，所以我们可以考虑只向左走的做法，再向右做一次。
再看看数据范围，大概是$n\log n$的做法。因为输入的轨道顺序与答案无关，所以我们可以先给他排个序。
------------
### **做法**
先考虑从左向右的做法：
我们先将轨道左端点按从小到大排序，这样的话枚举每条轨道的时候就可以实现从左到右遍历车站。我们用 $l$ 表示考虑这个轨道的左端点，$r$ 表示考虑这个轨道的右端点。
这样的话轨道可以分为四种：
$1.$ 全轨道都在 $x$ 点左边的，即 $r<x$。这个时候无论如何也到不了这个轨道上（因为是从左往右走），所以可以直接抛弃。
$2.$ 轨道里面包含了 $x$，即 $l\le x\le r$。这个时候可以到达 $r$，所以我们给 $r$ 打上一个能到达的标记。
$3.$ 轨道在 $x$ 的右边，但无法通过转线到达。这个时候我们可以和第一种一样抛弃。
$4.$ 轨道在 $x$ 的右边，但可以通过转线到达。显而易见，这个时候右边端点也能走到，所以我们给 $r$ 打上一个能到达的标记。现在问题来了，怎么区分第三种和第四种？我们发现，假如任意一条 $x$ 能转到的轨道 $p$ 里面包含了我们现在正在考虑的轨道的一部分，我们就能转到这条轨道上。因为我们是从左往右走的，所以我们可以设置一个变量 $rr$，表示我们目前最远能走到的右端点。每一次给 $r$ 打标记的时候令 ```rr=max(rr,r)``` 就可以了。这样当 $l>x$ 的时候，只要 $r\le rr$ 我们就判定它为第四种铁路。
代码如下：
```cpp
for(int i=1;i<=m;i++){
if(d[i].l<=x){
if(d[i].r>x){
is[d[i].r]=1;
rr=max(rr,d[i].r);
}
}
else if(d[i].l<=rr){
is[d[i].r]=1;
rr=max(rr,d[i].r);
}
}
```
对于从右向左的，只要把上面的反过来就行了。记得初始化 $lr$ 为无限大，每次取 ```min()```。
------------
### **接下来看完整代码吧**
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int lr=INT_MAX,rr,x,is[N],n,m;
struct node{
int l,r;
}d[N];
bool cmp1(node a,node b){
return a.l<b.l;
}
bool cmp2(node a,node b){
return a.r>b.r;
}
int main(){
// freopen("station.in","r",stdin);
// freopen("station.out","w",stdout);
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;i++){
scanf("%d%d",&d[i].l,&d[i].r);
if(d[i].l>d[i].r){
swap(d[i].l,d[i].r);
}
}
//printf("\n");
sort(d+1,d+1+m,cmp1);
for(int i=1;i<=m;i++){
if(d[i].l<=x){
if(d[i].r>x){
is[d[i].r]=1;
rr=max(rr,d[i].r);
}
}
else if(d[i].l<=rr){
is[d[i].r]=1;
rr=max(rr,d[i].r);
}
}
sort(d+1,d+1+m,cmp2);
for(int i=1;i<=m;i++){
if(d[i].r>=x){
if(d[i].l<x){
is[d[i].l]=1;
lr=min(lr,d[i].l);
}
}
else if(d[i].r>=lr){
is[d[i].l]=1;
lr=min(lr,d[i].l);
}
}
for(int i=1;i<=n;i++){
if(is[i]){
printf("%d ",i);
}
}
return 0;
}
```