Codeforces 786B Legacy 线段树优化建图

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

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

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

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

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

开启一扇从星球 vv 到星球 uu 的传送门；
开启一扇从星球 vv 到标号在 [l,r][l,r] 区间范围内任何一个星球的传送门。(即这扇传送门可以从一个星球出发通往多个星球)
开启一扇从标号在 [l,r][l,r] 区间范围内任何一个星球到星球 vv 的传送门。(即这扇传送门可以从多个星球出发到达同一个星球)
Rick 并不知道 Morty 在哪儿，但是 Unity 将要通知他 Morty 的具***置，并且他想要赶快找到通往所有星球的道路各一条并立刻出发。因此对于每一个星球(包括地球本身)他想要知道从地球到那个星球所需的最小钱数。

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

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

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

输出格式：
输出一行用空格隔开的 nn 个整数分别表示从地球到第 ii 个星球所需的最小钱数。

说明：在第一组测试样例里，Rick 可以先购买第 44 个方案再购买第 22 个方案从而到达标号为 22 的星球.

【数据范围】
对于 100%100% 的数据，1\le n,q \le 10^51≤n,q≤10
5
，1\le w \le 10^91≤w≤10
9

输入输出样例
输入 #1复制
3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17
输出 #1复制
0 28 12

输入 #2复制
4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16
输出 #2复制
0 -1 -1 12

什么是线段树优化建图呢？

当有一个点到一个区间，或者一个区间到点这种操作，因为我们不能暴力去连边，所以我们可以利用线段树来优化建图的过程，因为线段树对应了所有区间，但是节点数不多，故我们可以这样优化。

对于这道题，既有点到区间，又有区间到点，所以我们需要两颗线段树。

然后线段树用动态开点最好，因为我们有两颗树。

大概图形：

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=2e6+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,lc[N*20],rc[N*20],rt1,rt2,cnt,d[N<<2],vis[N<<2];
int head[N<<2],nex[M],to[M],w[M],tot;
inline void add(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
void build1(int &p,int l,int r){
	if(l==r)	return void(p=l);
	p=++cnt; int mid=l+r>>1;
	build1(lc[p],l,mid); build1(rc[p],mid+1,r);
	add(p,lc[p],0); add(p,rc[p],0);
}
void build2(int &p,int l,int r){
	if(l==r)	return void(p=l);
	p=++cnt; int mid=l+r>>1;
	build2(lc[p],l,mid); build2(rc[p],mid+1,r);
	add(lc[p],p,0); add(rc[p],p,0);
}
void link1(int p,int l,int r,int ql,int qr,int u,int w){
	if(l==ql&&r==qr) return void(add(u,p,w));
	int mid=l+r>>1;
	if(qr<=mid)	link1(lc[p],l,mid,ql,qr,u,w);
	else if(ql>mid)	link1(rc[p],mid+1,r,ql,qr,u,w);
	else	link1(lc[p],l,mid,ql,mid,u,w),link1(rc[p],mid+1,r,mid+1,qr,u,w);
}
void link2(int p,int l,int r,int ql,int qr,int u,int w){
	if(l==ql&&r==qr) return void(add(p,u,w));
	int mid=l+r>>1;
	if(qr<=mid)	link2(lc[p],l,mid,ql,qr,u,w);
	else if(ql>mid)	link2(rc[p],mid+1,r,ql,qr,u,w);
	else	link2(lc[p],l,mid,ql,mid,u,w),link2(rc[p],mid+1,r,mid+1,qr,u,w);
}

void dijkstra(int s){
	priority_queue<pair<int,int> > q;
	memset(d,0x3f,sizeof d); d[s]=0;	q.push({0,s});
	while(q.size()){
		int u=q.top().second; q.pop();
		if(vis[u])	continue;	vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			if(!vis[to[i]]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];	q.push({-d[to[i]],to[i]});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>s; cnt=n;
	build1(rt1,1,n); build2(rt2,1,n);
	while(m--){
		int op,v,u,w,l,r; scanf("%lld",&op);
		if(op==1)	scanf("%lld %lld %lld",&v,&u,&w),add(v,u,w);
		else if(op==2){
			scanf("%lld %lld %lld %lld",&v,&l,&r,&w); 
			link1(rt1,1,n,l,r,v,w);
		}else{
			scanf("%lld %lld %lld %lld",&v,&l,&r,&w); 
			link2(rt2,1,n,l,r,v,w);
		}
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)	printf("%lld ",d[i]==inf?-1:d[i]);puts("");
	return 0;
}