题解: 暴力建图当然gg 我们考虑用线段树分块建图的思想 因为涉及到两个区间 对着建图 一个线段树不够 考虑用两个线段树 一个作为出树(出树儿子向父亲连边) 一个作为入树(父亲向儿子连边) 每次出树向入树连边 这样建图的话也是mlogn^2的 显然还可以优化 我们采用对于每次连边 用一个超级大源点 这样的话每次连边为log^n级别的 然后对于入树而言 他可以和出树平行连边 这样的话 在本质上 还是两个区间直接产生贡献=>等价于从出树的x节点->入树的y节点->出树的y节点 这样连边跑spfa统计入树答案即可
#include <bits/stdc++.h>
#define mp make_pair
const int MAXN=8e5+10;
const int inf=1e9;
using namespace std;
vector<pair<int,int> >vec[MAXN<<3];
int pos[MAXN],sz,S,n,m,p;
void built(int rt,int l,int r){
if(l==r){pos[l]=rt;return ;}
vec[rt<<1].push_back(mp(rt,0));
vec[rt<<1|1].push_back(mp(rt,0));
int mid=(l+r)>>1;
built(rt<<1,l,mid);
built(rt<<1|1,mid+1,r);
}
void built1(int rt,int l,int r){
vec[rt+sz].push_back(mp(rt,0));
if(l==r)return ;
vec[rt+sz].push_back(mp((rt<<1)+sz,0));vec[rt+sz].push_back(mp((rt<<1|1)+sz,0));
int mid=(l+r)>>1;
built1(rt<<1,l,mid);
built1(rt<<1|1,mid+1,r);
}
void addedge(int rt,int l,int r,int ql,int qr,int vul){
if(ql<=l&&r<=qr){
if(vul>0)vec[rt].push_back(mp(S,1));
else vec[S].push_back(mp(rt+sz,0));
return ;
}
int mid=(l+r)>>1;
if(ql<=mid)addedge(rt<<1,l,mid,ql,qr,vul);
if(qr>mid)addedge(rt<<1|1,mid+1,r,ql,qr,vul);
}
int dis[MAXN<<3];bool vis[MAXN<<3];
queue<int>que;
void spfa(int t){
for(int i=0;i<=S;i++)dis[i]=inf,vis[i]=0;
que.push(t);vis[t]=1;dis[t]=dis[t+sz]=0;
while(!que.empty()){
int t1=que.front();que.pop();vis[t1]=0;
for(int i=0;i<vec[t1].size();i++){
if(dis[vec[t1][i].first]>dis[t1]+vec[t1][i].second){
dis[vec[t1][i].first]=dis[t1]+vec[t1][i].second;
if(!vis[vec[t1][i].first]){vis[vec[t1][i].first]=1;que.push(vec[t1][i].first);}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&p);S=(n<<3);
sz=(n<<2);built(1,1,n);built1(1,1,n);
int a,b,c,d;
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
S++;
addedge(1,1,n,a,b,1);addedge(1,1,n,c,d,0);
S++;
addedge(1,1,n,c,d,1);addedge(1,1,n,a,b,0);
}
spfa(pos[p]);
for(int i=1;i<=n;i++)printf("%d\n",dis[pos[i]+sz]);
}
原文：https://www.cnblogs.com/wang9897/p/9479086.html