P9166 [省选联考 2023] 火车站 题解

· · 题解

题目大意

在一个数轴上，有 n 个点和 m 个线段，当线段重合（包括端点）时，可以从一个线段转到另外一个线段，求出从点 x 出发，能够到达的线段端点.

思路简述

参考染色问题，故对于每次操作，即相当于在数轴上涂色，又因为在各个点可以更换线段，所以只需要用一种颜色上色，特别注意，本题要为线段涂色而不是对点涂色.

又因为题目要求求线段端点，所以对于每个线段的端点，将左右端点分别打上不同的标记，最后查询时，从 x 向左出发查询带左端点标记的点，同时，从 x 向右出发查询带右端点标记的点，排序后输出，注意查询时要求点之间的线段联通.

算法选择

本题为多次修改之后接一次查询，故我们可以采用修改复杂度 O(1)，查询复杂度 O(n) 的差分算法.

对于最后查询，向左查询时可以获得从大到小的答案，故可以倒序输出，向右查询时可以获得从小到大的答案，所以可以直接输出，此处可以减少一次排序操作.

参考代码

int n,m,x;
int qzh[200010];
int cf[200010];
int flag[200010];//01:L 10:R 11:L+R
const int L=1,R=2;
int ansl[200010],ansr[200010];
int cntl,cntr;
signed main(){
    n=read(),m=read(),x=read();
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        flag[l]|=L;
        flag[r]|=R;
        cf[l]++,cf[r]--;
    }
    for(int i=1;i<=n;i++){
        qzh[i]=qzh[i-1]+cf[i];
    }
    //to 1
    for(int i=x-1;i>=1;i--){
        if(!qzh[i])break;
        if(flag[i]&L)ansl[++cntl]=i;
    }
    //to n
    for(int i=x+1;i<=n;i++){
        if(!qzh[i-1])break;
        if(flag[i]&R)ansr[++cntr]=i;
    }
    for(int i=cntl;i>=1;i--){
        print(ansl[i]),putchar(' ');
    }
    for(int i=1;i<=cntr;i++){
        print(ansr[i]),putchar(' ');
    }
    return 0;
}

注释

为排版整洁，参考代码中略去了快读快写和头文件.

本文所指差分查询复杂度指查询预处理的复杂度，预处理后查询复杂度为 O(1).

算法时间复杂度 O(n+m).

本人为云省选，题解有不周到敬请谅解！

大概是最优解吧，66 ms Link.