[省选联考 2023]D1 题解

D1T1 P9166 火车站

观察题目，联系到以前做过的一些区间 dp 可以发现如果小 A 可以去到（这里是去到而不是最终停在） \(k\) 地点，那么 \(x\) 到 \(k\) 之间的所有地点他都可以去到，因为火车是连续的，不能跳着走，要来到当前地点必须到过路途中的所有节点。

这样子就好办了，分两次处理往左边和往右边走两种情况，这里讨论往右走的情况，往左同理。

我们对于每种情况处理他能去到的最右的地点，具体地，考虑在什么情况下，一个节点会去不了，不难得到处理完所有左端点早于这个节点的轨道后如果还到不了就是真的到不了。

于是我们按照左端点排序，如果遍历到的区间和当前答案区间有交集，就用遍历到的区间右端点更新当前的最右地点，最后判断每个铁轨的右端点在不在当前范围内即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector> 
#define ll long long
using namespace std;
struct Node{
	int l,r;
}a[2000005];
bool cmp(Node x,Node y){
	return x.l<y.l;
}
bool cmp2(Node x,Node y){
	return x.r<y.r;
}
int cnt[2000005];
int main(){
	int n,m,x;
	cin>>n>>m>>x;
	for(int i=1;i<=m;i++)cin>>a[i].l>>a[i].r;
	sort(a+1,a+m+1,cmp);
	int maxlen=x;
	for(int i=1;i<=m;i++){
		if(a[i].r<x || a[i].l>maxlen) continue;
		maxlen=max(maxlen,a[i].r);
	}
	for(int i=1;i<=m;i++) if(a[i].r<=maxlen && a[i].r>=x) cnt[a[i].r]++;
	sort(a+1,a+m+1,cmp2);
	int minlen=x;
	for(int i=m;i>=1;i--){
		if(a[i].l>x || a[i].r<minlen) continue;
		minlen=min(minlen,a[i].l);
	}
	for(int i=1;i<=m;i++) if(a[i].l>=minlen && a[i].l<=x) cnt[a[i].l]++;
	for(int i=1;i<=n;i++)if(i!=x && cnt[i]) cout<<i<<' ';
}