用的树剖和线段树区间取min

RT，MLE了。

一直没搞懂空间复杂度怎么算的，

有没有人帮我看看这个程序空间复杂度是多少？

如果能有大概的分析就更好

#include<bits/stdc++.h>
#define lson (spot<<1)
#define rson (spot<<1|1)
using namespace std;

const int maxn=50000+5,maxm=1e6+5;
const long long INF=1e10;

int n,m,root,k=0;
long long dis[maxn];
int idx=0,head[maxn];
struct edge {
	int v;
	long long w;
	int next;
}e[maxn<<1];
struct query {
	int u1,v1,u2,v2;
	long long w;
}q[maxm];

inline void Add(int u,int v,long long w) {
	e[++idx]={v,w,head[u]};
	head[u]=idx;
}

int siz[maxn],fa[maxn],dep[maxn],bigson[maxn];
int w[maxn],id[maxn],pos=0,top[maxn];

struct Segment_Tree {
	long long minn[maxn<<2];
	long long tag[maxn<<2];
	inline void pushdown(int spot) {
		if(tag[spot]==-1) return ;
		minn[lson]=min(minn[lson],tag[spot]);
		if(tag[lson]==-1) tag[lson]=tag[spot];
		else tag[lson]=min(tag[lson],tag[spot]);
		minn[rson]=min(minn[rson],tag[spot]);
		if(tag[rson]==-1) tag[rson]=tag[spot];
		else tag[rson]=min(tag[rson],tag[spot]);
		tag[spot]=-1;
	}
	void build(int spot,int L,int R) {
		tag[spot]=-1;
		if(L==R) {
			minn[spot]=dis[id[L]];
			return ;
		}
		int mid=(L+R)>>1;
		build(lson,L,mid);
		build(rson,mid+1,R);
		minn[spot]=min(minn[lson],minn[rson]);
	}
	void update(int spot,int L,int R,int x,int y,long long ne) { //区间取min 
		if(y<L||R<x) return ;
		if(x<=L&&R<=y) {
			minn[spot]=min(minn[spot],ne);
			if(tag[spot]==-1) tag[spot]=ne;
			else tag[spot]=min(tag[spot],ne);
			return ;
		}
		int mid=(L+R)>>1;
		update(lson,L,mid,x,y,ne);
		update(rson,mid+1,R,x,y,ne);
	}
	long long query(int spot,int L,int R,int x,int y) { //区间求min 
		if(y<L||R<x) return INF;
		if(x<=L&&R<=y) return minn[spot];
		pushdown(spot);
		int mid=(L+R)>>1;
		return min(query(lson,L,mid,x,y),query(rson,mid+1,R,x,y));
	}
	void ret(int spot,int L,int R) {
		if(L==R) {
			dis[id[L]]=minn[spot];
			return ;
		}
		pushdown(spot);
		int mid=(L+R)>>1;
		ret(lson,L,mid);
		ret(rson,mid+1,R);
	}
}T;

void dfs1(int now,int father,long long d) {
	dep[now]=dep[father]+1;
	siz[now]=1;
	fa[now]=father;
	dis[now]=d;
	for(int i=head[now];i;i=e[i].next) {
		int son=e[i].v;
		long long w=e[i].w;
		if(son==father) continue;
		dfs1(son,now,d+w);
		if(siz[bigson[now]]<siz[son]) bigson[now]=son;
		siz[now]+=siz[son];
	}
}

void dfs2(int now,int topv) {
	w[now]=++pos;
	id[pos]=now;
	top[now]=topv;
	if(bigson[now]) dfs2(bigson[now],topv);
	for(int i=head[now];i;i=e[i].next) {
		int son=e[i].v;
		if(son==fa[now]||son==bigson[now]) continue;
		dfs2(son,son);
	}
}

int f[maxn];
int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}

long long ask(int u,int v) {
	long long ret=INF;
	while(top[u]!=top[v]) {
		if(dep[top[u]]>=dep[top[v]]) {
			ret=min(ret,T.query(1,1,n,w[top[u]],w[u]));
			u=fa[top[u]];
		}
		else {
			ret=min(ret,T.query(1,1,n,w[top[v]],w[v]));
			v=fa[top[v]];
		}
	}
	if(w[u]<=w[v]) ret=min(ret,T.query(1,1,n,w[u],w[v]));
	else ret=min(ret,T.query(1,1,n,w[v],w[u]));
	return ret;
}

void modify(int u,int v,long long ne) {
	while(top[u]!=top[v]) {
		if(dep[top[u]]>=dep[top[v]]) {
			T.update(1,1,n,w[top[u]],w[u],ne);
			u=fa[top[u]];
		}
		else {
			T.update(1,1,n,w[top[v]],w[v],ne);
			v=fa[top[v]];
		}
	}
	if(w[u]<=w[v]) T.update(1,1,n,w[u],w[v],ne);
	else T.update(1,1,n,w[v],w[u],ne);
}

void dfs3(int now,long long w) {
	dis[now]=min(dis[now],dis[fa[now]]+w);
	for(int i=head[now];i;i=e[i].next) {
		int son=e[i].v;
		long long w=e[i].w;
		if(son==fa[now]) continue;
		dfs3(son,w);
	}
	dis[fa[now]]=min(dis[fa[now]],dis[now]+w);
}

int main() {
	scanf("%d%d%d",&n,&m,&root);
	for(int i=1;i<=n;i++) f[i]=i;
	while(m--) {
		int opt;
		scanf("%d",&opt);
		if(opt==1) {
			int u1,v1,u2,v2;
			long long w;
			scanf("%d%d%d%d%lld",&u1,&v1,&u2,&v2,&w);
			if(find(u1)==find(v1)&&find(u2)==find(v2)) {
				k++;
				q[k].u1=u1,q[k].v1=v1,q[k].u2=u2,q[k].v2=v2,q[k].w=w;
			}
		}
		else {
			int u,v;
			long long w;
			scanf("%d%d%lld",&u,&v,&w);
			Add(u,v,w);
			Add(v,u,w);
			f[find(u)]=find(v);
		}
	}
	for(int i=1;i<=n;i++) {
		int t1=find(root),t2=find(i);
		if(t1!=t2) {
			Add(root,i,INF);
			Add(i,root,INF);
		}
	}
	dfs1(root,0,0);
	dfs2(root,root);
	T.build(1,1,n);
	for(int i=1;i<=k;i++) {
		int u1=q[i].u1,v1=q[i].v1;
		int u2=q[i].u2,v2=q[i].v2;
		long long w=q[i].w;
		long long mn=ask(u1,v1);
		modify(u2,v2,mn+w);
	}
	T.ret(1,1,n);
	dfs3(root,0);
	for(int i=1;i<=n;i++)
		if(dis[i]>=INF) printf("-1 ");
		else printf("%lld ",dis[i]);
	return 0;
}