数据结构6——线段树优化建图

让我们先从一道题开始。

1、例题

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.

There are n planets in their universe numbered from 1 to n. Rick is in planet number s (the earth) and he doesn’t know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.

By default he can not open any portal by this gun. There are q plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.

Plans on the website have three types:

• With a plan of this type you can open a portal from planet v to planet u.
• With a plan of this type you can open a portal from planet v to any planet with index in range [l, r].
• With a plan of this type you can open a portal from any planet with index in range [l, r] to planet v.

Rick doesn’t known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

Input

The first line of input contains three integers n, q and s (1 ≤ n, q ≤ 105,1 ≤ s ≤ n) — number of planets, number of plans and index of earth respectively.

The next q lines contain the plans. Each line starts with a number t, type of that plan (1 ≤ t ≤ 3). If t = 1 then it is followed by three integers v,u and w where w is the cost of that plan (1 ≤ v, u ≤ n,1 ≤ w ≤ 109). Otherwise it is followed by four integers v,l,r and w where w is the cost of that plan (1 ≤ v ≤ n,1 ≤ l ≤ r ≤ n,1 ≤ w ≤ 109).

Output

In the first and only line of output print n integers separated by spaces. i-th of them should be minimum money to get from earth to i-th planet, or  - 1 if it’s impossible to get to that planet.

Examples

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

0 28 12

4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16

0 -1 -1 12

Note

In the first sample testcase, Rick can purchase 4th plan once and then 2nd plan in order to get to get to planet number 2.

中文大意

就是给定一张n个点的图，求源点s到每个点的单源最短路。
这张图共有q组边，连边方式有3种：

• a→b，边权为w的单向边；
• a→[l,r]，即a到连续区间[l,r]中的每一个点都有一条边权为w的边。
• [l,r]→a，即连续区间[l,r]中的每一个点都有一条到a边权为w的边。

注意数据范围n,q≤105。

2、解题思路

如果暴力连边（将一对多或者多对一的连边拆开分别连边），那么最差情况下，我们的边数将达到O(nq)级别，连边就直接超出能承受的范围——更不要说再跑最短路了。因此我们考虑如何使用一些数据结构把这些一对多的情况压缩成少数的一条边，使每一个连边操作都是O(1)的。
注意到所有“一对多”和“多对一“中“多”都是连续区间，回想我们平时处理连续区间的时候，最经常采用的一个数据结构就是线段树了。于是我们把线段树抓两棵过来放在那边。

那我们怎么用线段树呢？
我们在做区间加法的时候，遇到区间问题，我们都是往下查点，直到以这个点为根节点的子树完全包含于我们需要的区间内的时候，直接返回这个点的值——那么我们也可以采用同样的思想：如果我们把线段树的叶节点当做是原图的点，那么对于以这个点为根节点的子树的所有叶节点如果都在范围内，那么我们是不是可以直接在这个子树的根节点的地方连边呢?这样，对于这样一个子区间，我们只需要1条边。至于我们给出的一段区间会被拆成几个小区间，根据线段树的基本知识，我们知道它是常数级别的，因此我们连边就全部变成了O(1)的。

慢着，我们刚才说连边连在了线段树的中间，可是原图的点是叶节点，那么我们怎么才能走到中间的那些点呢？
于是我们就只好将每一个点向父节点连边，边权为0。这样就解决问题了？
并没有。因为我们连完边要跑最短路啊，如果我们都向父节点连边，那么中间代表区间的点又应该连向哪里呢?难道连向叶节点吗？这样只能解决多对一的问题，而一对多却不能解决。同样，如果由父节点连向儿子结点，也是不对的。
那么我们就开2棵线段树吧！我们令一颗叫做“入”树（intree），一棵叫做“出”树（outree），其中intree内部从下往上连0权边，outree内部从上往下连边0权边，那么我们对应的连边操作就是：

• 对于第一种，我们直接将intree对应u的叶节点连向outree对应v的点。
• 对于第二种，我们将intree对应a的叶节点连向一个或少数几个outree对应的代表区间的结点。
• 对于第三种，我们将一个或少数几个intree对应的代表区间的结点连向outree对应a的叶节点。
• 特别的，因为我们对于每个点在intree和outree都有直接对应的结点，他们实际上表示的是同一个东西，所以我们在intree和outree的叶节点之间对应的连上无向边。

最后，我们只需要跑一遍从intree的对应s结点跑一遍到outree对应所有结点的最短路即可。

时间复杂度：O((n+q)log2​n+最短路时间复杂度)，或者近似看做是O(qlog2​n)。
空间复杂度：O(n)。

代码如下：

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
const int MAXN=100010;
const int MAXM=1000010;
long long INF;

struct node{//segment_tree
	int id;
	int l,r;
}intree[MAXN<<2],outree[MAXN<<2];
struct edge{//graph::edge
	int v;
	long long w;
	edge *nxt;
	edge(){
		v=w=0;
		nxt=NULL;
	}
}*head[MAXM];

struct road{//dijkstra
	int i;
	long long dis;
	bool operator<(const road &rhs)const{
		return dis>rhs.dis;
	}
};
priority_queue<road>q;
int n,m,s;
int innum[MAXN],ounum[MAXN];
long long d[MAXM];
int vis[MAXM],cnt=0;

void adde(int u,int v,long long w){
	edge *p=new edge;
	p->v=v;p->w=w;
	p->nxt=head[u];
	head[u]=p;
}

int inbuild(int o,int l,int r){
	intree[o].l=l;intree[o].r=r;intree[o].id=cnt++;
	if(l==r)
		return innum[l]=intree[o].id;
	int mid=(l+r)>>1;
	adde(inbuild(lson(o),l,mid),intree[o].id,0);
	adde(inbuild(rson(o),mid+1,r),intree[o].id,0);
	return intree[o].id;
}
int oubuild(int o,int l,int r){
	outree[o].l=l;outree[o].r=r;outree[o].id=cnt++;
	if(l==r)
		return ounum[l]=outree[o].id;
	int mid=(l+r)>>1;
	adde(outree[o].id,oubuild(lson(o),l,mid),0);
	adde(outree[o].id,oubuild(rson@font-face {
				font-family: "autolinktags";
				src: url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff2") format("woff2"),
				url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff") format("woff"),
				url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.ttf") format("truetype");
				font-weight:normal;
				font-style:normal;
			}.tagslink::after { content:"\e613"; margin:2px 0 0 0px; font-size:12px; font-family:"autolinktags"; display:inline-block; vertical-align:top; }