线段树优化建图

起因

一般情况下，连边发生在两个点之间。
但在某些题目中，要在点和区间之间连边。
所以有了线段树优化建图。

原理

从模板题看起。
显然，直接暴力连边的最坏时间复杂度和空间复杂度都为 \(O(n^2)\)。
线段树建图的原理就是建出线段树，区间连边转化为向线段树上的节点连边。

但只是如图所示的连边是不够的，对于区间中的所有点都要连边。
所以父子节点之间连边权为 \(0\) 的边就能解决问题了。
至于连边的方向由要求决定。

• 如果要求点向区间连边，线段树上就从父节点向子节点连边，目标点向线段树上节点连边。
• 如果要求区间向点连边，线段树上就从子节点向父节点连边，线段树上节点向目标点连边。

还有一个小细节点：编号问题。
如果直接按照朴素方法建出线段树，则树上节点的编号可能会与题目中的节点编号产生冲突。
解决方法是，利用类似于动态开点线段树的写法，每个线段树节点从 \(n\) 开始分配，其中叶子节点的编号就是区间本身，也就省去了某些写法要在两棵线段树的叶子节点之间连边的操作。
建树的代码：

void b1(int &p,int l,int r){if(l==r){p=l;return ;}p=++tot;MID b1(ls[p],l,m);b1(rs[p],m+1,r);I(p,ls[p]),I(p,rs[p]);}
void b2(int &p,int l,int r){if(l==r){p=l;return ;}p=++tot;MID b2(ls[p],l,m);b2(rs[p],m+1,r);I(ls[p],p),I(rs[p],p);}

看回到题目，题目要求点之间连边，点向区间连边，区间向点连边，求最短路。
建出两棵线段树，然后按要求连边即可。

#include 
#define int long long
#define MID int m=(l+r)>>1;
#define V e[i].v
using namespace std;int rd(){
	int w=0,v=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')v=-1;c=getchar();}
	while(c>='0'&&c<='9'){w=(w<<1)+(w<<3)+(c&15);c=getchar();}return w*v;
}const int N=2e6+100,INF=0x3f3f3f3f3f3f;int v[N],a[N],ls[N],rs[N],d[N],n,m,s,r1,r2;priority_queue >q;
struct E{int v,w,nt;}e[N];int fir[N],c,tot;void I(int u,int v,int w=0){e[++c].w=w;e[c].v=v;e[c].nt=fir[u];fir[u]=c;}
void b1(int &p,int l,int r){if(l==r){p=l;return ;}p=++tot;MID b1(ls[p],l,m);b1(rs[p],m+1,r);I(p,ls[p]),I(p,rs[p]);}
void b2(int &p,int l,int r){if(l==r){p=l;return ;}p=++tot;MID b2(ls[p],l,m);b2(rs[p],m+1,r);I(ls[p],p),I(rs[p],p);}
void C(int p,int l,int r,int L,int R,int x,int z,int f){
	if(l>=L&&r<=R){if(f)I(x,p,z);else I(p,x,z);return ;}MID 
	if(L<=m)C(ls[p],l,m,L,R,x,z,f);if(R>m)C(rs[p],m+1,r,L,R,x,z,f);return ;
}void dj(int s){
	memset(d,0x3f,sizeof(d));d[s]=0;q.push(make_pair(0,s));	while(!q.empty()){
		int x=q.top().second;q.pop();if(v[x])continue;v[x]=1;
		for(int i=fir[x];i;i=e[i].nt)if(d[V]>d[x]+e[i].w)d[V]=d[x]+e[i].w,q.push(make_pair(-d[V],V));
}}signed main(){
	n=rd(),m=rd(),s=rd();tot=n;b1(r1,1,n);b2(r2,1,n);
	for(int i=1,o,x,y,z,L,R;i<=m;i++){
		o=rd();if(o==1)x=rd(),y=rd(),z=rd(),I(x,y,z);
		else{x=rd(),L=rd(),R=rd(),z=rd();if(o==2)C(r1,1,n,L,R,x,z,1);else C(r2,1,n,L,R,x,z,0);}
	}dj(s);for(int i=1;i<=n;i++)cout<<((d[i]