#PQJ1198x6311. QOJ 1198_6311
QOJ 1198_6311
NOI2022 省选 DAY1 火车站(station) 火车站(station) 【题目描述】 有n 个火车站排成一条直线,从1 到n 编号。一共有m 条火车轨道,每条轨道覆 盖一段火车站区间[li, ri]。 对于一个被多条火车轨道覆盖的火车站,火车在经过这里的时候,可以在此处改变 轨道。但是火车无法掉头,只能朝着一个方向运行(即只能一直往1 的方向开或者一直 往n 的方向开)。 小A 从火车站x 出发,即搭上了经过x 的任意一列火车(这列火车也可能是从车 站x 出发)。这列火车可能行驶在火车站x 所处的任一条轨道上,其运行方向既可能是 往1 的方向开,也可能是往n 的方向开。小A 上车后就开始昏睡,直到乘坐的火车到 达某条线路的终点站停下,他才醒过来。问小A 最后可能到达的车站。 注意:火车应运行至少一个车站,且火车切换轨道后不会立刻停下来,而是会继续 沿着当前轨道前进。 【输入格式】 从文件station.in 中读入数据。 输入的第一行包含三个正整数n, m, x,分别表示火车站的数量,火车轨道的数量 以及小A 初始的起点。 接下来m 行,每行包含两个正整数li, ri,表示一条火车轨道运行的区间。 【输出格式】 输出到文件station.out 中。 输出一行,包含若干个用单个空格分隔的正整数,表示小A 最后可能到达的车站, 按照车站编号升序排序输出。 【样例1 输入】 1 7 5 4 2 3 4 3 4 6 4 1 3 5 5 7 6 4 6 第2 页 共9 页
NOI2022 省选 DAY1 火车站(station) 【样例1 输出】 1 1 3 6 7 【样例1 解释】 火车从车站4 出发,沿着第一条轨道可以运行到终点3,也可以接着沿第三条轨道 运行到终点1。 火车从车站4 出发,沿着第二条轨道可以运行到终点6,也可以在车站5 换到第四 条轨道运行到终点7。 所以最终按顺序输出1, 3, 6, 7。 【样例2】 见选手目录下的station/station2.in 与station/station2.ans。 【样例3】 见选手目录下的station/station3.in 与station/station3.ans。 【样例4】 见选手目录下的station/station4.in 与station/station4.ans。 【数据范围】 对于所有的数据,保证1 ≤n, m ≤2 × 105;1 ≤x ≤n;1 ≤li < ri ≤n。 测试点 n, m ≤ 特殊性质 1 50 无 2 3 5000 4 5 6 2 × 105 A 7 8 无 9 10 特殊性质A:保证x = 1。 第3 页 共9 页