线段树优化建图

线段树优化建图

这是利用线段树优化建图的算法，当出现区间1->n的区间连边操作时，一般的图就需要O(n)的复杂度，但是利用线段树就可以做到O(logn),很好用。

例题

题意

Rick 和他的同事们做出了一种新的带放射性的婴儿食品(???根据图片和原文的确如此...)，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。

在宇宙中一共有 n 个星球标号为 1∼n。Rick 现在身处于标号为 s 的星球(地球)但是他不知道 Morty 在哪里。

众所周知，Rick 有一个传送枪，他用这把枪可以制造出一个从他所在的星球通往其他星球(也包括自己所在的星球)的单行道路。但是由于他还在用免费版，因此这把枪的使用是有限制的。

默认情况下他不能用这把枪开启任何传送门。在网络上有 q 个售卖这些传送枪的使用方案。每一次你想要实施这个方案时你都可以购买它，但是每次购买后只能使用一次。每个方案的购买次数都是无限的。

网络上一共有三种方案可供购买：

• 开启一扇从星球 v 到星球 u的传送门；
• 开启一扇从星球 v 到标号在[l,r] 区间范围内任何一个星球的传送门。(即这扇传送门可以从一个星球出发通往多个星球)
• 开启一扇从标号在 [l,r] 区间范围内任何一个星球到星球 v 的传送门。(即这扇传送门可以从多个星球出发到达同一个星球)

Rick 并不知道 Morty 在哪儿，但是 Unity 将要通知他 Morty 的具体位置，并且他想要赶快找到通往所有星球的道路各一条并立刻出发。因此对于每一个星球(包括地球本身)他想要知道从地球到那个星球所需的最小钱数。

输入数据：

输入数据的第一行包括三个整数 n，q 和 s 分别表示星球的数目，可供购买的方案数目以及地球的标号。

接下来的 q 行表示 q 种方案。

• 输入 1 v u w 表示第一种方案，其中 v,u 意思同上，w 表示此方案价格。
• 输入 2 v l r w 表示第二种方案，其中 v,l,r 意思同上，w 表示此方案价格。
• 输入 3 v l r w 表示第三种方案，其中 v,l,r 意思同上，w 表示此方案价格。

输出格式：

输出一行用空格隔开的 n 个整数分别表示从地球到第 i 个星球所需的最小钱数。如果不能到达那个星球，输出-1。

参考题解

题解的思路很明白了，我也想重新整理一遍，但是画图很麻烦呢，找到好的方法之后再来吧。

文字讲解一下思路，如果我们已经按照题目要求建好边，那么问题就是一个简单的单源最短路问题，用最短路的算法就可以解决。于是我们就考虑建边，对于单点建边，也和一般的图问题一样。所以这道题目我们只考虑区间建边。对于区间操作，我们想到的有，差分，前缀和，线段树。可以在这道题使用的就是线段树了。思考线段树的结构，要连接点和区间，只要按线段树查询的方式就可以logn地找到区间并连边。这样，区间节点可以向下连接到子节点。

但是我们并不能直接在一个线段树上建边。父节点与子节点如果建双向边，并且父子节点理应无消耗，那么叶节点之间可以无消耗穿梭。

因此要建单向边。单独思考操作二，我们要建从叶子节点到区间节点的边，而区间节点要可以向下到具体的点，因此我们就要建一棵从根节点指向叶子节点的树，并有一些从叶子节点指向区间节点的边。同理，单独考虑操作三，就要建一棵从叶子节点指向根节点的树，并有一些从区间节点指向叶子节点的边。两者结合，就要建两棵线段树，并把对应的叶子节点相连。

建树

const int N=5e5;
int leaf[2*N+10],dis[2*N+10];
void build(int x,int l,int r){//建树
	if(l==r){
		leaf[l]=x;//叶节点标号
		return;
	}
    //建图，单向树
	t[x].push_back(pii(ls,0));
	t[x].push_back(pii(rs,0));
	t[ls+N].push_back(pii(x+N,0));
	t[rs+N].push_back(pii(x+N,0));
	build(ls,l,mid);
	build(rs,mid+1,r);
}

连边

void connect(int x,int l,int r,int L,int R,int u,int w,int f){
	if(l>=L&&r<=R){
		if(f)t[x+N].push_back(pii(u,w));//操作三 区间指向叶节点
		else t[u].push_back(pii(x,w));//操作二 叶节点指向区间
        //需要注意的是叶节点本质相同，所以全连同一棵树上的叶子节点即可
		return;
	}
	if(L<=mid)connect(ls,l,mid,L,R,u,w,f);
	if(mid<R)connect(rs,mid+1,r,L,R,u,w,f);
}

完整代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ls (2*x)
#define rs (2*x+1)
#define mid ((l+r)/2)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
const int N=5e5;
const int inf=1e18;
int leaf[2*N+10],dis[2*N+10];
int n,m,st;
vector<pair<int,int> >t[2*N];
void build(int x,int l,int r){
	if(l==r){
		leaf[l]=x;
		return;
	}
	t[x].push_back(pii(ls,0));
	t[x].push_back(pii(rs,0));
	t[ls+N].push_back(pii(x+N,0));
	t[rs+N].push_back(pii(x+N,0));
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void connect(int x,int l,int r,int L,int R,int u,int w,int f){
	if(l>=L&&r<=R){
		if(f)t[x+N].push_back(pii(u,w));
		else t[u].push_back(pii(x,w));
		return;
	}
	if(L<=mid)connect(ls,l,mid,L,R,u,w,f);
	if(mid<R)connect(rs,mid+1,r,L,R,u,w,f);
}
signed main(){
	cin>>n>>m>>st;
	build(1,1,n);
	while(m--){
		int op,u,v,l,r,w;
		cin>>op;
		if(op==1){
			cin>>u>>v>>w;
			t[leaf[u]].push_back(pii(leaf[v],w));
		}else{
			cin>>u>>l>>r>>w;
			connect(1,1,n,l,r,leaf[u],w,op%2);
		} 
	}
	for(int i=1;i<=n;i++){
		t[leaf[i]].push_back(pii(leaf[i]+N,0));
		t[leaf[i]+N].push_back(pii(leaf[i],0));
	}
	priority_queue<pii,vector<pii>,greater<pii> >q;
	for(int i=0;i<2*N+10;i++)dis[i]=inf;
	dis[leaf[st]+N]=0;
	q.push(pii(0,leaf[st]+N));
	while(!q.empty()){
		pii u=q.top();
		q.pop();
		int x=u.se,sum=u.fi;
		//cout<<x<<'\n';
		if(sum>dis[x])continue;
		for(auto v:t[x]){
			int y=v.fi,z=v.se;
			if(dis[y]>sum+z){
				dis[y]=sum+z;
				q.push(pii(dis[y],y));
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[leaf[i]]==inf)cout<<"-1 ";
		else cout<<dis[leaf[i]]<<' ';
	}
	return 0;
}