新技能get✔。
线段树优化建边主要是针对一类连续区间和连续区间之间建边的题，建边非常的优秀。。
这题中，每次要求$[l1,r1]$每一点向$[l2,r2]$每一点建无向边，然后单元最短路。
暴力建边，边数$O(n^2m)$，时空双炸。
优化一点的建边，对于一个区间的点，把他们统一向一个虚点连零边，再从这个虚点向另一个区间每一个点连一条带权边。这样，每一条路径都是可以通过这个来表示的。边数$O(nm)$，仍然不行。
然后，采用线段树的优秀的“将区间拆分成不超过$\log n$个小区间”的性质，对于$n$个点，建两颗线段树$A,B$，$A$称作入树，$B$称作出树。他们的叶子就是所有的$n$个点，上面的非叶点就是区间。。（先假设是单向的边）然后，对于一次区间向另一区间的连边，从出树$B$拆分出来的对应的$\log n$个区间代表的点分别向一个新开的虚点连一条有向0边，再从这个虚点向入树$A$对应的另一个区间拆分的若干小区间点连带权边，这样实现了区间连边。但是，这只是区间整体连边了，还要保证点与点连通，只要把出树$B$每个点从孩子向父亲连有向0边，入树$A$每个点从父亲向孩子连有向0边，就表示一个点通过“爬”到一个区间点，走过虚点，在下来走到另外一个目标点这样一个过程。最后，走进入树后，为了可以继续走，从$A$向$B$的每一个代表相同区间的点连0边，表示再过去。
有一个dalao的图可能会解释的非常清晰。。附上地址
线段树优化建边大致就是这个原理。然后直接从底层叶子开始为源点跑dij就行了。
然后个人觉得很多代码很繁。。偶尔看到一种写法，对每个点编一个号，把AB两树底层叶子编号直接合并成一个，省去了两树之间的相互建边。。这样码量就小很多了。具体还是看代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define mst(x) memset(x,0,sizeof x)
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=5e5+;
int n,m,s,cnt;
struct thxorz{
int head[N*],nxt[N*],to[N*],w[N*],tot;
inline void add(int x,int y,int z){to[++tot]=y,nxt[tot]=head[x],head[x]=tot,w[tot]=z;}
}G;
struct SGT{
int id[N<<];
#define lc i<<1
#define rc i<<1|1
void build(int i,int L,int R,int dir){
if(L==R){id[i]=L;return;}
id[i]=++cnt;int mid=L+R>>;//dbg2(i,cnt),dbg2(L,R);
build(lc,L,mid,dir),build(rc,mid+,R,dir);
if(!dir)G.add(id[i],id[lc],),G.add(id[i],id[rc],);
else G.add(id[lc],id[i],),G.add(id[rc],id[i],);
}
void update(int i,int L,int R,int ql,int qr,int dir){
if(ql<=L&&qr>=R){dir?G.add(cnt,id[i],):G.add(id[i],cnt,);return;}
int mid=L+R>>;
if(ql<=mid)update(lc,L,mid,ql,qr,dir);
if(qr>mid)update(rc,mid+,R,ql,qr,dir);
}
}A,B;
priority_queue<pii,vector<pii>,greater<pii> > pq;
int dis[N*];
#define y G.to[j]
inline void dij(){
memset(dis,0x3f,sizeof dis);pq.push(make_pair(dis[s]=,s));
while(!pq.empty()){
int d=pq.top().first,x=pq.top().second;pq.pop();
if(dis[x]^d)continue;
for(register int j=G.head[x];j;j=G.nxt[j])if(MIN(dis[y],d+G.w[j]))pq.push(make_pair(dis[y],y));
}
}
#undef y
int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
cnt=read(n),read(m),read(s);
A.build(,,n,),B.build(,,n,);
for(register int i=,l1,r1,l2,r2;i<=m;++i){
read(l1),read(r1),read(l2),read(r2);
++cnt,B.update(,,n,l2,r2,),A.update(,,n,l1,r1,);
++cnt,B.update(,,n,l1,r1,),A.update(,,n,l2,r2,);
}
dij();
for(register int i=;i<=n;++i)printf("%d\n",dis[i]);
return ;
}
不过，这题鉴于全是0/1边，所以直接一个0/1BFS就可以线性解决了。。并没有快多少可能是deque的锅。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define mst(x) memset(x,0,sizeof x)
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=5e5+;
int n,m,s,cnt;
struct thxorz{
int head[N*],nxt[N*],to[N*],w[N*],tot;
inline void add(int x,int y,int z){to[++tot]=y,nxt[tot]=head[x],head[x]=tot,w[tot]=z;}
}G;
struct SGT{
int id[N<<];
#define lc i<<1
#define rc i<<1|1
void build(int i,int L,int R,int dir){
if(L==R){id[i]=L;return;}
id[i]=++cnt;int mid=L+R>>;//dbg2(i,cnt),dbg2(L,R);
build(lc,L,mid,dir),build(rc,mid+,R,dir);
if(!dir)G.add(id[i],id[lc],),G.add(id[i],id[rc],);
else G.add(id[lc],id[i],),G.add(id[rc],id[i],);
}
void update(int i,int L,int R,int ql,int qr,int dir){
if(ql<=L&&qr>=R){dir?G.add(cnt,id[i],):G.add(id[i],cnt,);return;}
int mid=L+R>>;
if(ql<=mid)update(lc,L,mid,ql,qr,dir);
if(qr>mid)update(rc,mid+,R,ql,qr,dir);
}
}A,B;
deque<pii> q;
int dis[N*];
#define y G.to[j]
inline void dij(){
memset(dis,0x3f,sizeof dis);q.push_back(make_pair(dis[s]=,s));
while(!q.empty()){
int d=q.front().first,x=q.front().second;q.pop_front();
if(d^dis[x])continue;
for(register int j=G.head[x];j;j=G.nxt[j])if(MIN(dis[y],d+G.w[j]))
G.w[j]?q.push_back(make_pair(dis[y],y)):q.push_front(make_pair(dis[y],y));
}
}
#undef y
int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
cnt=read(n),read(m),read(s);
A.build(,,n,),B.build(,,n,);
for(register int i=,l1,r1,l2,r2;i<=m;++i){
read(l1),read(r1),read(l2),read(r2);
++cnt,B.update(,,n,l2,r2,),A.update(,,n,l1,r1,);
++cnt,B.update(,,n,l1,r1,),A.update(,,n,l2,r2,);
}
dij();
for(register int i=;i<=n;++i)printf("%d\n",dis[i]);
return ;
}
总结：区间建边，线段树。。