题目链接：nowcoder多校8-Explorer

题意：

给一个无向图，每条边上有一个区间限制，只有在区间内的数能够通过该边，问从1号点出发，有多少数能到达n号点。

题解：

线段树维护区间，用并查集维护点的连通性。

对于每条边上的区间，将其离散化之后加入线段树中，然后从根节点开始向下dfs，把同一区间内的边取出来，判断1号点与n号点是否连通，并查集需要按秩合并进行优化。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5;
int n, m, ans;
int fa[MAXN], sz[MAXN];
int uu[MAXN], vv[MAXN], ll[MAXN], rr[MAXN], tmp[MAXN << 2];
vector<int> a[MAXN << 3];
int getf(int x)
{
    if (x == fa[x])
        return x;
    return getf(fa[x]);
}
void seg_update(int L, int R, int val, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        a[rt].push_back(val);
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid)
        seg_update(L, R, val, l, mid, rt << 1);
    if (R > mid)
        seg_update(L, R, val, mid + 1, r, rt << 1 | 1);
}
void dfs(int l, int r, int rt)
{
    vector<int> vec;
    vec.clear();
    for (int i = 0; i < a[rt].size(); i++)
    {
        int now = a[rt][i];
        int u = uu[now], v = vv[now];
        u = getf(u), v = getf(v); //并查集按秩合并
        if (sz[u] > sz[v])
            swap(u, v);
        fa[u] = v;
        sz[v] += sz[u];
        vec.push_back(u);
    }
    int mid = (l + r) >> 1;
    if (getf(1) == getf(n))
        ans += tmp[r + 1] - tmp[l];
    else if (l < r)
    {
        dfs(l, mid, rt << 1);
        dfs(mid + 1, r, rt << 1 | 1);
    }
    for (int i = 0; i < vec.size(); i++)
    {
        int x = vec[i];
        fa[x] = x;
    }
    vec.clear();
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        fa[i] = i, sz[i] = 1;
    int cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d%d", &uu[i], &vv[i], &ll[i], &rr[i]);
        tmp[++cnt] = ll[i];
        tmp[++cnt] = rr[i] + 1;
    }
    sort(tmp + 1, tmp + 1 + cnt);
    cnt = unique(tmp + 1, tmp + 1 + cnt) - (tmp + 1);
    for (int i = 1; i <= m; i++)
    {
        ll[i] = lower_bound(tmp + 1, tmp + 1 + cnt, ll[i]) - tmp;
        rr[i] = lower_bound(tmp + 1, tmp + 1 + cnt, rr[i] + 1) - tmp;
        seg_update(ll[i], rr[i] - 1, i, 1, cnt - 1, 1);
    }
    dfs(1, cnt - 1, 1);
    printf("%d\n", ans);
    return 0;
}