C++(clang++11) 解法, 执行用时: 812ms, 内存消耗: 35576K, 提交时间: 2020-10-24 12:25:50

#include<bits/stdc++.h>
#include<vector>
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
using namespace std;
const int N=100005;
int n,m,U[N],V[N],L[N],R[N],fa[N],sz[N],ans;
vector<int>v,e[N<<3];
int find(int x){return fa[x]==x?x:find(fa[x]);}
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void update(int u,int l,int r,int x,int y,int val){
	if(x<=l&&r<=y){
		e[u].push_back(val);
		return;
	}int mid=(l+r)>>1;
	if(x<=mid)update(lson,x,y,val);
	if(y>mid)update(rson,x,y,val);
}
void dfs(int u,int l,int r){
	vector<int>lst;int mid=(l+r)>>1;
	for(int i=0;i<(int)e[u].size();i++){
		int x=U[e[u][i]],y=V[e[u][i]],fx=find(x),fy=find(y);
		if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;
		lst.push_back(fx);fa[fx]=fy;sz[fy]+=sz[fx];
	}if(find(1)==find(n))ans+=v[r]-v[l-1];
	else if(l<r){dfs(u<<1,l,mid);dfs(u<<1|1,mid+1,r);}
	for(int i=lst.size()-1;~i;i--)fa[lst[i]]=lst[i];
	lst.clear();
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&U[i],&V[i],&L[i],&R[i]);
		v.push_back(L[i]);v.push_back(R[i]+1);
	}sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++){
		fa[i]=i;sz[i]=1;
	}
	for(int i=1;i<=m;i++){
		update(1,1,v.size(),getid(L[i]),getid(R[i]+1)-1,i);
	}dfs(1,1,v.size());printf("%d\n",ans);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 922ms, 内存消耗: 35648K, 提交时间: 2019-08-13 10:03:34

#include<bits/stdc++.h>
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
using namespace std;
const int N=100005;
int n,m,U[N],V[N],L[N],R[N],fa[N],sz[N],ans;
vector<int>v,e[N<<3];
int find(int x){return fa[x]==x?x:find(fa[x]);}
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void update(int u,int l,int r,int x,int y,int val){
	if(x<=l&&r<=y){
		e[u].push_back(val);
		return;
	}int mid=(l+r)>>1;
	if(x<=mid)update(lson,x,y,val);
	if(y>mid)update(rson,x,y,val);
}
void dfs(int u,int l,int r){
	vector<int>lst;int mid=(l+r)>>1;
	for(int i=0;i<(int)e[u].size();i++){
		int x=U[e[u][i]],y=V[e[u][i]],fx=find(x),fy=find(y);
		if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;
		lst.push_back(fx);fa[fx]=fy;sz[fy]+=sz[fx];
	}if(find(1)==find(n))ans+=v[r]-v[l-1];
	else if(l<r){dfs(u<<1,l,mid);dfs(u<<1|1,mid+1,r);}
	for(int i=lst.size()-1;~i;i--)fa[lst[i]]=lst[i];
	lst.clear();
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&U[i],&V[i],&L[i],&R[i]);
		v.push_back(L[i]);v.push_back(R[i]+1);
	}sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++){
		fa[i]=i;sz[i]=1;
	}
	for(int i=1;i<=m;i++){
		update(1,1,v.size(),getid(L[i]),getid(R[i]+1)-1,i);
	}dfs(1,1,v.size());printf("%d\n",ans);
	return 0;
}