洛谷P6348 [PA2011]Journeys 题解

题目链接：P6348 [PA2011]Journeys

题意：

给定 $n$ 个结点， $m$ 次操作

每次操作给出 $a,b,c,d$ ，表示

$$\forall x\in [a,b],\forall y\in [c,d], \exist (x,y) \in E\land (y,x) \in E$$

也就是编号在 $[a,b]$ 内的所有结点与编号在 $[c,d]$ 内的结点存在边权为 $1$ 的无向边

求 $s$ 到每个点的最短路。

$1\le n\le 5\times 10^5$，$1\le m\le 10^5$，$1\le a\le b\le n$，$1\le c\le d\le n$。

线段树优化建图板子（区间连区间），不会单点连区间的戳这里

同样的，我们还是建两棵树，称为「入树」和「出树」

先考虑连有向边的情况。

对于区间的修改，我们只需要把入树和出树中的结点提出来

称出树中提取的结点构成 $S$ ，入树中提取的结点构成 $T$

我们新建一个虚点 $u$ ，把 $S$ 中的每个结点向 $u$ 连一条边权为 $0$ 的有向边

然后再把 $u$ 向 $T$ 中的每个结点分别连一条边权为 $1$ 的有向边

然后这道题要连无向边，所以我们反过来再做一次就行了

注意！反过来的时候一定要再建一个虚点，不然会出错！（显然）

纯文本可能不是很好懂，所以放张图。

这道题因为边权只有 $0,1$ ，考虑 $\mathtt{01bfs}$

时间复杂度 $O((n+m)\log n)$

空间复杂度 $O(2n\log n + 2m)$

代码：（常数比较大）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define DEBUG puts("-------------")
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(5e5+15))
#define M ((int)(1e5+15))

const int D=2e6+15;
const int D2=N*8+255;
int n,m,s,cnt,d[N*8+255+M*2],a[N*8+255];
bitset<N*8+255+M*2> vis;
struct node1{int v,w;};
struct show_l_r{int l,r;}tr[N<<2];
vector<node1> g[N*8+255+M*2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
void build(int l,int r,int at)
{
    tr[at].l=l; tr[at].r=r;
    if(l==r) return a[l]=at, void(0);
    int mid=(l+r)>>1;
    g[at].push_back({ls(at),0});
    g[at].push_back({rs(at),0});
    g[ls(at)+D].push_back({at+D,0});
    g[rs(at)+D].push_back({at+D,0});
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
}
void link(int nl,int nr,int tu,int w,int opt,int at)
{
    int l=tr[at].l,r=tr[at].r;
    if(nl<=l&&r<=nr)
    {
        if(opt) g[at+D].push_back({tu,w});
        else g[tu].push_back({at,w});
        return;
    }
    int mid=(l+r)>>1;
    if(nl<=mid) link(nl,nr,tu,w,opt,ls(at));
    if(nr>mid) link(nl,nr,tu,w,opt,rs(at));
}
deque<int> q;
void _01bfs(int st)
{
    memset(d,0x3f,sizeof(d));
    d[st]=0; q.push_back(st);
    while(!q.empty())
    {
        int u=q.front(); q.pop_front();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i : g[u])
        {
            int v=i.v,w=i.w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                if(!w) q.push_front(v);
                else q.push_back(v);
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m); read(s);
    build(1,n,1);
    for(int i=1,l1,r1,l2,r2,s1,s2; i<=m; i++)
    {
        read(l1); read(r1); read(l2); read(r2);
        // void link(int nl, int nr, int tu, int w, int opt, int at)
        s1=i*2-1+D2,s2=i*2+D2;
        link(l1,r1,s1,0,1,1);
        link(l2,r2,s1,1,0,1);
        link(l2,r2,s2,0,1,1);
        link(l1,r1,s2,1,0,1);
    }
    for(int i=1; i<=n; i++)
    {
        g[a[i]].push_back({a[i]+D,0}),
        g[a[i]+D].push_back({a[i],0});
    }
    _01bfs(a[s]+D);
    for(int i=1; i<=n; i++)
        write(d[a[i]]!=INF ? d[a[i]] : -1),pc('\n');
    return 0;
}