E - Explorer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
typedef pair<int,int> P;
struct N{
	int l,r,u,v;
}a[maxn];
int n,m;
int dep[maxn],pre[maxn],ans,tot;
int b[maxn];
vector<int> tr[maxn<<2];
int getf(int t){
	while(t!=pre[t]){
		t = pre[t];
	}
	return pre[t];
}
void update(int rt,int l,int r,int L,int R,int k){
	if(L<=l&&R>=r){
		tr[rt].push_back(k); 
		return ;
	}
	int mid = (l+r)>>1;
	if(L<=mid)update(rt<<1,l,mid,L,R,k);
	if(R>mid)update(rt<<1|1,mid+1,r,L,R,k);
}
void dfs(int rt,int l,int r){
	int sz = tr[rt].size();
	vector<P> tmp;
	for(int i=0;i<sz;i++){
		int t = tr[rt][i];
		int u = a[t].u, v = a[t].v;
		u = getf(u);	v = getf(v);
		if(u==v)continue;
		if(dep[u]<dep[v])
			pre[u] =  v, tmp.push_back(P{u,0});
		else if(dep[v]<dep[u])
			pre[v] = u, tmp.push_back(P{v,0});
		else 
			pre[u] = v,dep[v]++,tmp.push_back(P{u,1}); 
	}
	if(getf(1)==getf(n)){
		ans+=b[r+1] - b[l];
	}else if(l<r){
		int mid = (l+r)>>1;
		dfs(rt<<1,l,mid);
		dfs(rt<<1|1,mid+1,r);
	} 
	sz = tmp.size();
	for(int i = sz-1;i>=0;i--){
		P o = tmp[i];
		dep[ pre[o.first] ]-=o.second;
		pre[ o.first ] = o.first;
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		pre[i] = i;
		dep[i] = 0;
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d %d %d",&a[i].u,&a[i].v,&a[i].l,&a[i].r);
		b[2*i-1] = a[i].l;
		b[2*i] = a[i].r + 1;
	} 
	sort(b+1,b+1+2*m);
	tot = unique(b+1,b+1+2*m) - b - 1;
	for(int i=1;i<=m;i++){
		a[i].l = lower_bound(b+1,b+1+tot,a[i].l) - b;
		a[i].r = lower_bound(b+1,b+1+tot,a[i].r+1) - b - 1;
		update(1,1,tot,a[i].l,a[i].r,i);	
	}
	dfs(1,1,tot);
	printf("%d\n",ans);
	return 0;
}