P9166题解

简单题，但是我考场写炸了。\(100\rightarrow70\)。

我们读入的时候，先开两个数组 \(ls,rs\) 来记录当前这个点是否为某条线段左端点或右端点。

我们发现，每一条线段都是连续的，因此可以直接差分记录当前这个点能否走到。

然后你提交上去发现你能过。

实际上这种做法是假的。

为什么呢？

如果遇到 \([1,2],[3,4]\) 这样的线段，实际上 \(1\) 号点是无法到达 \(4\) 号点的，但是直接差分是能直接到达。

因此差分的正解是应该处理的时候把下标乘 \(2\) 以此来制造空点。

时间复杂度 \(O(n)\)。

为什么有人考场会把这道题写炸啊。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,x;
int cf[200010<<1];
int a[200010<<1];
int ls[200010],rs[200010];
bool vis[200010];
int ans[200010],tot;
int main()
{
    scanf("%d%d%d",&n,&m,&x);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        ls[l]=1,rs[r]=1;
        cf[(l<<1)-1]++,cf[r<<1]--;
    }
    for(int i=1;i<=n<<1;i++) a[i]=a[i-1]+cf[i];
    for(int i=(x<<1)-1;i<=n<<1;i++)
    {
        if(a[i]<=0) break;
        if(rs[(i+1)>>1]&&!vis[(i+1)>>1]&&((i+1)>>1)!=x)
        {
            vis[(i+1)>>1]=1;
            ans[++tot]=(i+1)>>1;
        } 
    }
    for(int i=(x<<1)-1;i>=1;i--)
    {
        if(a[i]<=0) break;
        if(ls[(i+1)>>1]&&!vis[(i+1)>>1]&&((i+1)>>1)!=x)
        {
            vis[(i+1)>>1]=1;
            ans[++tot]=(i+1)>>1;
        }
    }
    sort(ans+1,ans+1+tot);
    for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
    return 0;
}