线段树优化建图

问题：
CF786B
给定一个\(n\)个点，\(m\)次连边的有向图，有三种连边（均有边权）方式：
1.\(u\to v\)，一条\(u\)指向\(v\)的连边。
2.\(u\to [l,r]\)，\(u\)向在区间\([l,r]\)的点分别连一条边。
3.\([l,r]\to v\)，在区间\([l,r]\)的点向\(v\)分别连一条边。
问从\(1\)点出发，到各个点的最短路。
思路:
这里是用线段树优化建图trick，就是如果每次2和3的操作\([l,r]\)都是\([1,n]\)，建边的数量就是\(n\times m\)。这里类比求区间和，可以使用线段树，将一个点向一个线段树上的点连边，每次连\(\log_{2} n\)条边。线段树上的点再连上它在线段树上的子节点，叶子节点就直接连图上的对应点，就能与2和3操作等效。注意：要建一棵自上而下的线段树和一颗自下而上的线段树。
代码:

#include<iostream>
#include<vector>
#include<queue>
#define int long long
#define INF 1000000000000000000
using namespace std;
int kd(){
	int x=0,f=1;
	char a=getchar();
	while(a<'0'||a>'9'){
		if(a=='-'){
			f=-1;
		}
		a=getchar();
	}
	while(a>='0'&&a<='9'){
		x=x*10+a-'0';
		a=getchar();
	}
	return x*f;
}
int n,q,s;
struct node{
	int l,r;
}tree[400010];
struct nod{
	int to;
	int nxt;
	int val;
}edge[4000010];
int head[1000010],tot;
void addedge(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].nxt=head[u];
	edge[tot].val=w;
	head[u]=tot;
}
void build(int i,int l,int r){
	tree[i].l=l;
	tree[i].r=r;
	if(l==r){
		addedge(i,l+8*n,0);
		addedge(l+8*n,i+4*n,0);
		return ;
	}
	int mid=(l+r)/2;
	addedge(i,i*2,0);
	addedge(i,i*2+1,0);
	addedge(i*2+4*n,i+4*n,0);
	addedge(i*2+1+4*n,i+4*n,0);
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	return ;
}
void search1(int i,int l,int r,int k,int w){
	if(tree[i].l>=l&&tree[i].r<=r){
		addedge(k+8*n,i,w);
		return ;
	}
	if(tree[i*2].r>=l){
		search1(i*2,l,r,k,w);
	}
	if(tree[i*2+1].l<=r){
		search1(i*2+1,l,r,k,w);
	}
}
void search2(int i,int l,int r,int k,int w){
	if(tree[i].l>=l&&tree[i].r<=r){
		addedge(i+4*n,k+8*n,w);
		return ;
	}
	if(tree[i*2].r>=l){
		search2(i*2,l,r,k,w);
	}
	if(tree[i*2+1].l<=r){
		search2(i*2+1,l,r,k,w);
	}
}
int dis[1000010];
bool vis[1000010];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > dui;
void dij(){
	dui.push(make_pair(0,8*n+s));
	while(!dui.empty()){
		int u=dui.top().second;
		dui.pop();
		if(vis[u]==1){
			continue;
		}
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(vis[v]==1){
				continue;
			}
			if(dis[v]>dis[u]+edge[i].val){
				dis[v]=dis[u]+edge[i].val;
				dui.push(make_pair(dis[v],v));
			}
		}
	}
}
signed main(){
	cin>>n>>q>>s;
	build(1,1,n);
	while(q--){
		int opt;
		opt=kd();
		if(opt==1){
			int u,v,w;
			u=kd();v=kd();w=kd();
			addedge(u+8*n,v+8*n,w);
		}
		if(opt==2){
			int u,l,r,w;
			u=kd();l=kd();r=kd();w=kd();
			search1(1,l,r,u,w); 
		}
		if(opt==3){
			int v,l,r,w;
			v=kd();l=kd();r=kd();w=kd();
			search2(1,l,r,v,w);
		}
	}
	for(int i=1;i<=9*n;i++){
		dis[i]=INF;
	}
	dis[8*n+s]=0;
	dij();
	for(int i=1;i<=n;i++){
		if(dis[8*n+i]==INF){
			printf("-1 ");
		}
		else{
			printf("%lld ",dis[8*n+i]);
		}
	}
	return 0;
}