Description
一个星球上有 \(n\) 个国家和许多双向道路，国家用 \(1 \sim n\) 编号。
但是道路实在太多了，不能用通常的方法表示。于是我们以如下方式表示道路: \((a, b),(c, d)\) 表示，对于任意两个国家 \(x, y\)，如果 \(a \leq x \leq b, c \leq y \leq d\)，那么在 \(x,y\) 之间有一条道路。
首都位于 \(P\) 号国家。你想知道 \(P\) 号国家到任意一个国家最少需要经过几条道路。保证 \(P\) 号国家能到任意一个国家。
Solution
朴素的建边方法是将区间内的点连向一个虚点。但这样做的边数是 \(2nm\)。注意到区间建边具有包含性，即如果 \((l,r)\) 可以到达包含 \((l,r)\) 的区间 \((L,R)\) 能到达的点。那么对于区间 \((a,b)\) 中的点 \(x\) 和区间 \((c,d)\) 中的点 \(y\) 的边，可以通过建 \(x\to[a,b]\to k\to[c,d]\to y\) 的几条边（\(k\) 是虚点）来做到。
因此考虑将区间放到线段树上。建出两个线段树，记为入树和出树。入树上父节点往子节点连边，出树上子节点往父节点连边。入树的叶子节点向出树的对应叶子节点连边。这些边的边权为 \(0\)。然后对于题目中的每条边，建出树区间 \(\to\) 虚点 \(\to\) 入树区间的边，边权为 \(1\)。然后从起点开始跑最短路或者 01bfs。
Code
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define N 500005
#define M 100005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,st,trsz,cnt,id[N],dis[N*10];
bool bj[N*10];
struct seg
{
int l,r,id,v,lson,rson;
}tr[N<<3];
struct edge {int to,val;};
struct node
{
int x,dis;
bool operator>(const node& x) const {return dis>x.dis;}
};
vector<edge> g[N<<3];
priority_queue<node,vector<node>,greater<node>> q;
void build_in(int x,int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1;
build_in(x<<1,l,mid);build_in(x<<1|1,mid+1,r);
g[x].push_back((edge){x<<1,0});
g[x].push_back((edge){x<<1|1,0});
}
void build_out(int x,int l,int r)
{
g[x].push_back((edge){trsz+x,0});
if (l==r) {id[l]=x+trsz;return;}
int mid=(l+r)>>1;
build_out(x<<1,l,mid);build_out(x<<1|1,mid+1,r);
g[(x<<1)+trsz].push_back((edge){x+trsz,0});
g[(x<<1|1)+trsz].push_back((edge){x+trsz,0});
}
void add(int x,int l,int r,int p,int q,int k)
{
if (l>=p&&r<=q)
{
g[k].push_back((edge){x,1});
if (k&1) g[x+trsz].push_back((edge){k+1,1});
else g[x+trsz].push_back((edge){k-1,1});
return;
}
int mid=(l+r)>>1;
if (p<=mid) add(x<<1,l,mid,p,q,k);
if (q>mid) add(x<<1|1,mid+1,r,p,q,k);
}
int main()
{
scanf("%d%d%d",&n,&m,&st);
trsz=n*4;
build_in(1,1,n);
build_out(1,1,n);
cnt=trsz*2;
for (int i=1;i<=m;++i)
{
int x,y,u,v;
scanf("%d%d%d%d",&x,&y,&u,&v);
cnt+=2;
add(1,1,n,x,y,cnt-1);
add(1,1,n,u,v,cnt);
}
memset(dis,inf,sizeof(dis));
dis[id[st]]=0;q.push((node){id[st],0});
while (!q.empty())
{
int x=q.top().x;q.pop();
if (bj[x]) continue;
bj[x]=true;
for (int i=0;i<g[x].size();++i)
{
int y=g[x][i].to,z=g[x][i].val;
if (dis[y]>dis[x]+z)
{
dis[y]=dis[x]+z;
if (!bj[y]) q.push((node){y,dis[y]});
}
}
}
for (int i=1;i<=n;++i)
printf("%d\n",dis[id[i]]/2);
return 0;
}