P9166题解

黑部奈叶香 · 2023-04-13 12:16:20 · 题解

因为考场的时候不会正解，所以提供一种暴力做法。

首先两个有交点的区间合并之后显然还是连续，因此考虑分别维护向左走和向右走的答案。

不断暴力扫描所有区间，对于一个区间，如果能与当前区间合并且不完全位于当前区间的右边则合并区间，然后将区间端点加入答案即可，然后标记此区间，当没有区间被选中则结束，向右走同理。注意初始区间是 [x,x] ，而 x 不能被加入答案。

这么做的时间复杂度最差是 \mathcal{O}(m^2) 的，但是随机数据跑不满可以通过。hack 数据可以直接构造一堆长度为 2 的区间。

考场代码：

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int now=0;
    char ch=getchar();
    while(!isdigit(ch))
    ch=getchar();
    while(isdigit(ch))
    now=now*10+ch-'0',ch=getchar();
    return now;
}
vector<int>ans;
const int maxn=2e6+10;
int l[maxn],r[maxn],n,m,x;
bool vis[maxn];
int query_merge(int l1,int l2,int r1,int r2)
{
    return (min(r1,r2)-max(l1,l2)>=0);
}
int vis2[maxn];
void add(int k)
{
        if(k==x)
        return;
    if(!vis2[k])
    ans.push_back(k),vis2[k]=1;
}
void calc_left()
{
    bool ok=1;
    int nowl=x,nowr=x;
    while(ok)
    {
        ok=0;
        for(int i=1;i<=m;i++)
        if(!vis[i])
        {
            if(query_merge(nowl,l[i],nowr,r[i]))
            nowl=min(nowl,l[i]),add(l[i]),vis[i]=1,ok=1;
        }
    }
}
void calc_right()
{
    memset(vis,0,sizeof vis);
    bool ok=1;
    int nowl=x,nowr=x;
    while(ok)
    {
        ok=0;
        for(int i=1;i<=m;i++)
        if(!vis[i])
        {
            if(query_merge(nowl,l[i],nowr,r[i]))
            nowr=max(nowr,r[i]),add(r[i]),vis[i]=1,ok=1;
        }
    }
}
main()
{
        //freopen("station.in","r",stdin);
        //freopen("station.out","w",stdout);
    n=read(),m=read(),x=read();
    for(int i=1;i<=m;i++)
    l[i]=read(),r[i]=read();
    calc_left();
    calc_right();
    sort(ans.begin(),ans.end());
    for(auto x:ans)
    cout<<x<<' ';
}
/*
7 5 4
3 4
4 6
1 3
5 7
4 6
*/