P9166题解

· · 题解

模拟大法好！

今年省选赛时看了旁边神仙一眼，第一题用了 300 多行代码写了个线段树 ，赛后发现还有使用并查集和树状数组的人，但是个人认为此题没有这么麻烦，我们直接采用模拟的方式来完成这一题。

简化题意

由于原题面有点复杂，因此我稍微化简题意：给定 m 条线段，覆盖点 x 的线段我们定义为该线段合法，与合法的线段有任何重合的线段也合法（包括端点重合），求合法线段的端点。

解法

首先通过分析样例我们可以得到这样一张图：

（图丑请见谅）

看完这张图片也许你会有一个疑问，为什么 5 号点是合法线段端点，却不是正确答案呢？再次阅读题目后，我们知道：火车无法掉头，只能朝着一个方向运行，也就是说，火车是往 7 号点的方向开去的，不能掉头或者瞬间停下到 5 号点。由此我们可以得出结论：

在处理完之后，我们就要把步骤退回来求合法线段了，我们假设你正在玩搭桥游戏，有很多木板可以搭桥，那么你搭桥的形状一定是这样的：

由上图我们发现每一块木板的端点一定是在上一块木板上，那么我们可以用这个思路寻找合法线段，首先定义 l,r 分别是合法线段的最大左端点和最大右端点，如果说一个线段的左端点或者右端点处于这个区间内（即与合法线段重合），那么这个线段也合法，于是我们可以使用两个循环，分别求出 l,r 的最值，即：

F1(i,1,n) if(a[i].l>=mini&&a[i].l<=maxi) maxi=max(maxi,a[i].r);//线段左端点位于合法区间内，该线段合法，更新右端点的最值
F2(i,n,1) if(a[i].r>=mini&&a[i].r<=maxi) mini=min(mini,a[i].l);//同上，但是需要倒推，因为线段排序后的上升性，后面有讲

（为了方便理解，将 l,r 换成了 mini,maxi ）

当然，当某一条线段覆盖了 x 号点时，根据前面的定义那么该线段是合法的，左右端点都是答案，所以也要更新最两端的大值，即：

if(a[i].l<=x&&x<=a[i].r){//覆盖 x 号点
        mini=min(mini,a[i].l);//取最值
        maxi=max(maxi,a[i].r);
        v[a[i].l]=v[a[i].r]=1;//标记合法
}

在完成以上处理之后，如果一条线段没有完全覆盖在 l,r 之间时，这一条线段一定不合法。

最后根据上面搭桥的那一张图片，我们发现从左到右的每一块木板的左端点和右端点一定是不下降的，首先来看一张图：

我们发现第 3 条线段应该是合法的，但是由于我们遍历线段的顺序是按照编号的，所以它的遍历顺序应该是左，右，中。此时第 3 条线段就不合法了，因为它与唯一的合法线段也就是第 1 条线段没有重合部分。

然后我们对线段进行排序后，就得到了下面这张图片：

此时第 3 条线段就是合法的，因为它与第 2 条线段有重合部分，而第 2 条线段又与合法线段 1 有重合部分，由此我们可以得出结论：线段要采取排序，从而保证端点的不下降性

最后输出时我们套用上第一步的样例结论做最后的特判即可（还需要标记数组给答案打标记，说明此点是合法线段的端点），后面是代码部分：

#include<bits/stdc++.h>
#define ll long long
#define F1(i,j,n) for(int i=j;i<=n;i++)
#define F2(i,j,n) for(int i=j;i>=n;i--)
using namespace std;
const int N=1e6+10,NN=1e4+10;
ll n,m,k,x,y,u,w,cnt=0,ans=0,t=0,l,r,len,T;
ll mini=INT_MAX,maxi=0,Mod;
bool v[N];
struct Node{
    ll l,r; 
}a[N];
bool cmp(Node a,Node b){
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}
int main(){
    cin>>m>>n>>x; 
    F1(i,1,n){
        cin>>a[i].l>>a[i].r;//双端编号
        if(a[i].l<=x&&x<=a[i].r){//覆盖x号点，即合法区间 
            mini=min(mini,a[i].l);//更新合法端点最值 
            maxi=max(maxi,a[i].r);
            v[a[i].l]=v[a[i].r]=1;//线段两端标记为答案 
        } 
    }
    sort(a+1,a+1+n,cmp);//排序 
    F1(i,1,n) if(a[i].l>=mini&&a[i].l<=maxi) maxi=max(maxi,a[i].r);//左端与合法线段有重合部分，更新最大值
    F2(i,n,1) if(a[i].r>=mini&&a[i].r<=maxi) mini=min(mini,a[i].l);//右端与合法线段有重合部分，更新最大值
    F1(i,1,n){
        if(a[i].l<mini||a[i].r>maxi) continue;//不是合法线段 
        if(a[i].r<x) v[a[i].l]=1;//由结论得，该合法线段在x号点左边时，左端点是答案 
        else v[a[i].r]=1;//同上 
    }
    F1(i,1,m) if(v[i]&&i!=x) cout<<i<<" ";//此编号标记为答案且不是起点 
    return 0;
}