P9166 [省选联考 2023] 火车站 tj

xcrr · 2023-04-12 20:10:38 · 题解

分析题意，我们可以发现一个做法：

• 每个点记录两个数 l,r，l 代表覆盖这个节点的所有区间的左端点中，距离最远（最左）的一个，r 代表覆盖它的所有区间的右端点中，距离最远（最右）的一个。
• 我们从 x 出发，分别做向左走到头和向右走到头的情况。我用向左走举例：我们从 x 一个一个向左扫，维护一个数 t，代表当前走过的节点更换若干次轨道，能到达最远（最左）点的编号。每个节点都有可能导致 t 的更新：

设当前节点为 now，如果 l_{now} < t，那么更新 t=l_{now}。

这个不难理解。首先，我们可以发现，我们的路程中，要想到一个节点，从起点到这个节点之间的所有节点都要走过；又因为我们能到 now 点，从 now 最远能到 l_{now} 点，如果 l_{now}<t，就意味着从起点 x 最远能到 l_{now} 点而不再是 t 点，那么就需要用这个点更新 t。

• 只要我们没有走到 t，我们就一直走，因为一定能走，边走边进行上述更新。因为所有的 l_{now} 构成了终点站的集合，记录下它们，就是答案。
• 向右走的情况同理。整个模拟的过程时间复杂度是 O(n)。
• 现在我们要求 l,r，发现更改产生于读入区间时，而且不过是区间更改最大最小值的操作。我的做法是用线段树。时间复杂度 O(m\log n)。

线段树代码量略大，但是很好想。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=2e5+10;
int nl[N],nr[N];
int n,m,x;
const int inf=0x3f3f3f3f;
struct nod{
    int l,r,lazy,mx;
}tl[N<<2];
struct nod2{
    int l,r,lazy,mn;
}tr[N<<2];
void lpushdown(int x)
{
    int lz=tl[x].lazy;
    tl[x].lazy=0;
    int l=(x<<1),r=(x<<1|1);
    tl[l].lazy=max(tl[l].lazy,lz);
    tl[l].mx=max(tl[l].mx,lz);
    tl[r].lazy=max(tl[r].lazy,lz);
    tl[r].mx=max(tl[r].mx,lz);
}
void rpushdown(int x)
{
    int lz=tr[x].lazy;
    tr[x].lazy=inf;
    int l=(x<<1),r=(x<<1|1);
    tr[l].lazy=min(tr[l].lazy,lz);
    tr[l].mn=min(tr[l].mn,lz);
    tr[r].lazy=min(tr[r].lazy,lz);
    tr[r].mn=min(tr[r].mn,lz);
}
void lbuild(int id,int l,int r)
{
    tl[id].l=l,tl[id].r=r;
    if(l==r)return;
    int mid=l+r>>1;
    lbuild(id<<1,l,mid);
    lbuild(id<<1|1,mid+1,r);
    tl[id].mx=max(tl[id<<1].mx,tl[id<<1|1].mx);
}
void rbuild(int id,int l,int r)
{
    tr[id].l=l,tr[id].r=r;tr[id].lazy=tr[id].mn=inf;
    if(l==r)return;
    int mid=l+r>>1;
    rbuild(id<<1,l,mid);
    rbuild(id<<1|1,mid+1,r);
    tr[id].mn=min(tr[id<<1].mn,tr[id<<1|1].mn);
}
void updl(int l,int r,int id,int d)
{
    if(tl[id].l>=l&&tl[id].r<=r){tl[id].mx=max(tl[id].mx,d),tl[id].lazy=max(tl[id].lazy,d);return;}
    lpushdown(id);
    int mid=tl[id].l+tl[id].r>>1;
    if(l<=mid)updl(l,r,id<<1,d);
    if(r>mid)updl(l,r,id<<1|1,d);
    tl[id].mx=max(tl[id<<1].mx,tl[id<<1|1].mx);
}
void updr(int l,int r,int id,int d)
{
    if(tr[id].l>=l&&tr[id].r<=r){tr[id].mn=min(tr[id].mn,d),tr[id].lazy=min(tr[id].lazy,d);return;}
    rpushdown(id);
    int mid=tr[id].l+tr[id].r>>1;
    if(l<=mid)updr(l,r,id<<1,d);
    if(r>mid)updr(l,r,id<<1|1,d);
    tr[id].mn=min(tr[id<<1].mn,tr[id<<1|1].mn);
}
void askl(int id)
{
    if(tl[id].l==tl[id].r)
    {
        nl[tl[id].l]=tl[id].mx;
        return;
    }lpushdown(id);
    askl(id<<1);
    askl(id<<1|1);
}
void askr(int id)
{
    if(tr[id].l==tr[id].r)
    {
        nr[tr[id].l]=tr[id].mn;
        return;
    }rpushdown(id);
    askr(id<<1);
    askr(id<<1|1);
}
int main()
{
    cin>>n>>m>>x;
    lbuild(1,1,n);
    rbuild(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        updl(u+1,v,1,u);
        updr(u,v-1,1,v);
    }
    askl(1),askr(1);
    if(nl[x]==0&&nr[x]==inf)return 0;
    set<int>ans;
    if(nl[x]!=0)ans.insert(nl[x]);
    if(nr[x]!=inf)ans.insert(nr[x]);
    int mn=nl[x];
    if(mn!=0)
    for(int i=x-1;i>=mn;i--)
    {
        if(nl[i]!=0)
        ans.insert(nl[i]);
        if(nl[i]!=0)
        mn=min(mn,nl[i]);
    }
    int mx=nr[x];
    if(mx!=inf)
    for(int i=x+1;i<=mx;i++)
    {
        if(nr[i]!=inf)
        ans.insert(nr[i]);
        if(nr[i]!=inf)
        mx=max(mx,nr[i]);
    }
    for(auto cc:ans)if(cc!=x)cout<<cc<<' ';
}