Explorer - 题解

标签与难度

标签: 数据结构, 线段树, 并查集, 分治, 离线处理, 坐标离散化难度: 2300

题目大意喵~

各位探险家们，大家好喵~！这次我们来到了一个神奇的关卡，这里有 $N$ 个地点和 $M$ 条双向道路。

每条路都像是一个挑剔的传送门，它连接着两个地点 $u$ 和 $v$ ，但只有当我们的“体型”在某个特定区间 $[l, r]$ 内时，才能通过它，喵！体型太小会被小动物欺负，体型太大又会卡住，真是麻烦呐。

我们的任务是从地点 1 出发，到达终点 $N$ 。在出发前，我们可以喝下一种魔法药水，将自己的体型固定成任意一个正整数。

现在的问题是：有多少个不同的正整数体型，可以让我们成功地从地点 1 走到地点 $N$ 呢？请帮帮 Gromah 和 LZR 算出来吧，喵~

解题思路分析

这道题问的是“有多少种体型可以从 1 到 $N$ ”，体型的取值范围可能非常大（最大到 $10^9$ ），我们肯定不能一个一个体型去试，那样本喵的爪子都要算冒烟了也算不完的，呜~

所以，我们需要找到更聪明的办法，呐！

从暴力到优化，喵~

我们来观察一下，对于一条路 $(u, v, l, r)$ ，它是否能走，只取决于我们的体型 size 是否满足 $l \le \text{size} \le r$ 。

这意味着，当我们的体型从 size 变成 size+1 时，地图上可用的道路集合通常是不会变的。只有当体型跨过某个 $l_i$ 或者 $r_i$ 时，可用的道路才会发生增加或减少。这些 $l_i$ 和 $r_i$ 就是“关键点”！

更准确地说，当体型等于 $l_i$ 时，第 $i$ 条路变得可用；当体型大于 $r_i$ （即等于 $r_i+1$ ）时，第 $i$ 条路又变得不可用。所以，真正的“事件发生点”是所有道路的 $l_i$ 和 $r_i+1$ 。

我们可以把所有这些“事件点”收集起来，排序并去重，得到一系列离散的点 $d_1, d_2, \dots, d_k$ 。这些点把整个数轴划分成了一段段的区间 $[d_j, d_{j+1}-1]$ 。在任何一个这样的区间内，我们任选一个体型，它所能使用的道路集合是完全相同的！

这给了我们一个新思路：

把所有边的 $l_i$ 和 $r_i+1$ 收集起来，排序去重，得到离散化后的坐标点数组 d。
遍历这些坐标点构成的每一个小区间 $[d_j, d_{j+1}-1]$ 。
对于每个区间，随便挑一个代表（比如 $d_j$ ），构建出此时可用的图。
用并查集（DSU）检查点 1 和点 $N$ 是否连通。
如果连通，那么这个区间里的所有体型 d[j+1] - d[j] 个都是可行的，把这个数量加入总答案。

但是...这个方法还是有点慢，喵。离散化后我们最多有 $2M$ 个点，也就是 $O(M)$ 个区间。对于每个区间，我们都要遍历全部 $M$ 条边来判断是否可用，然后构建并查集。总复杂度大约是 $O(M^2 \alpha(N))$ ，对于 $M=2 \cdot 10^5$ 来说，还是会超时。

线段树分治 + 可撤销并查集！

问题的瓶颈在于，我们在每个区间都重复计算了连通性。能不能让信息继承下去呢？

注意到每条边 $(u, v, l, r)$ 的“有效期”是一个连续的体型区间 $[l, r]$ 。这正好对应了我们离散化后的坐标轴上的一段区间！一个操作在某个区间上生效，这不就是线段树最擅长的事情嘛，喵！

我们可以这样来设计最终的算法：

坐标离散化: 和之前的想法一样，收集所有 $l_i$ 和 $r_i+1$ ，排序去重得到 $d_1, \dots, d_k$ 。我们的“时间轴”就是这些离散点构成的 $k-1$ 个基本区间。
线段树: 建立一棵线段树，代表 1 到 k-1 这些区间的索引。线段树的每个节点都将拥有一个 vector，用来存放“完全覆盖”这个节点所代表的区间的边。
区间更新: 对于每一条边 $(u, v, l_i, r_i)$ ，它在体型区间 $[l_i, r_i]$ 内有效。我们找到 $[l_i, r_i]$ 在离散化坐标中对应的索引区间 [L, R]。然后，我们把这条边 (u, v) 插入到线段树中，让它存在于代表 [L, R] 的那些节点上。这是一种经典的线段树区间更新操作，每条边会被分散到 $O(\log M)$ 个节点上。
DFS 遍历与可撤销并查集:
- 我们从线段树的根节点开始进行深度优先搜索（DFS）。
- 进入一个节点时，我们将这个节点 vector 中存放的所有边，通过并查集的 unite 操作合并。
- 如果这个节点是叶子节点，它就代表了一个基本区间 $[d_j, d_{j+1}-1]$ 。此时，我们检查 1 和 $N$ 是否在同一个集合里。如果是，就给总答案加上区间的长度 $d_{j+1}-d_j$ 。
- 然后，我们继续递归地访问它的子节点。
- 最关键的一步：当从一个节点的所有子树都访问完毕，准备回溯返回到父节点时，我们必须撤销在进入这个节点时所做的所有并查集合并操作，恢复并查集到进入此节点之前的状态！

为了实现“撤销”，我们需要一个“可撤销并-查集”。普通的带路径压缩的并查集很难撤销。一个简单的实现方法是：

使用按秩合并（或按大小合并），但不进行路径压缩（或者只在 find 中做，但 unite 时要小心）。
每次 unite 操作修改了 parent 数组或 rank 数组时，都将“修改的地址”和“修改前的值”存入一个栈（历史记录）中。
回溯时，从栈中弹出相应数量的记录，并根据记录恢复数组的值。

这样一来，我们就像带着一个状态可回滚的并查集，在整棵线段树上进行了一次时空旅行，巧妙地计算出了所有可行体型的总数，喵~

代码实现

这是本喵根据上面的思路，精心重构的一份代码哦~ 希望能帮到你，喵！

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// 定义边的结构体，u, v 是顶点，l, r 是体型区间
struct Edge {
    int u, v, l, r;
};

// 用来存储并查集回滚操作的历史记录
struct DSU_History {
    int* ptr; // 修改的变量地址
    int old_value; // 修改前的值
};

// 全局变量声明，喵~
const int MAXN = 200005;
int n; // 顶点数
long long total_valid_sizes = 0; // 最终答案

// --- 可撤销并查集 ---
int parent[MAXN];
int sz[MAXN]; // 按大小合并
std::vector<DSU_History> history;

// 查找根节点 (带路径压缩)
int find_set(int v) {
    if (v == parent[v])
        return v;
    return find_set(parent[v]);
}

// 合并两个集合，并记录操作
void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (sz[a] < sz[b]) std::swap(a, b);
        
        // 记录对 parent[b] 的修改
        history.push_back({&parent[b], parent[b]});
        parent[b] = a;
        
        // 记录对 sz[a] 的修改
        history.push_back({&sz[a], sz[a]});
        sz[a] += sz[b];
    }
}

// 撤销操作直到某个时间点
void rollback(int checkpoint) {
    while (history.size() > checkpoint) {
        DSU_History last_op = history.back();
        *last_op.ptr = last_op.old_value;
        history.pop_back();
    }
}

// --- 线段树 ---
std::vector<std::pair<int, int>> seg_tree[4 * MAXN * 2]; // 存边 (u, v)

// 向线段树的 [L, R] 区间添加一条边
void add_edge_to_segtree(int v, int tl, int tr, int l, int r, std::pair<int, int> edge) {
    if (l > r) return;
    if (l == tl && r == tr) {
        seg_tree[v].push_back(edge);
        return;
    }
    int tm = tl + (tr - tl) / 2;
    add_edge_to_segtree(v * 2, tl, tm, l, std::min(r, tm), edge);
    add_edge_to_segtree(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, edge);
}

// DFS 遍历线段树
void solve_dfs(int v, int tl, int tr, const std::vector<int>& discrete_points) {
    int checkpoint = history.size(); // 记录进入此节点前的历史状态

    // 合并当前节点的所有边
    for (const auto& edge : seg_tree[v]) {
        unite_sets(edge.first, edge.second);
    }

    if (tl == tr) {
        // 到达叶子节点，代表一个基本区间 [d_tl, d_{tl+1}-1]
        if (find_set(1) == find_set(n)) {
            total_valid_sizes += (long long)discrete_points[tl + 1] - discrete_points[tl];
        }
    } else {
        // 递归访问子节点
        int tm = tl + (tr - tl) / 2;
        solve_dfs(v * 2, tl, tm, discrete_points);
        solve_dfs(v * 2 + 1, tm + 1, tr, discrete_points);
    }

    // 回溯，撤销操作
    rollback(checkpoint);
}


int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int m;
    std::cin >> n >> m;

    std::vector<Edge> edges(m);
    std::vector<int> discrete_points;
    for (int i = 0; i < m; ++i) {
        std::cin >> edges[i].u >> edges[i].v >> edges[i].l >> edges[i].r;
        discrete_points.push_back(edges[i].l);
        discrete_points.push_back(edges[i].r + 1);
    }

    // 坐标离散化
    std::sort(discrete_points.begin(), discrete_points.end());
    discrete_points.erase(std::unique(discrete_points.begin(), discrete_points.end()), discrete_points.end());

    // 将边添加到线段树
    for (const auto& edge : edges) {
        auto it_l = std::lower_bound(discrete_points.begin(), discrete_points.end(), edge.l);
        auto it_r = std::lower_bound(discrete_points.begin(), discrete_points.end(), edge.r + 1);
        int l_idx = std::distance(discrete_points.begin(), it_l);
        int r_idx = std::distance(discrete_points.begin(), it_r) - 1;
        add_edge_to_segtree(1, 0, discrete_points.size() - 2, l_idx, r_idx, {edge.u, edge.v});
    }

    // 初始化并查集
    for(int i = 1; i <= n; ++i) {
        parent[i] = i;
        sz[i] = 1;
    }

    // 从线段树根节点开始解决问题
    if (!discrete_points.empty() && discrete_points.size() > 1) {
       solve_dfs(1, 0, discrete_points.size() - 2, discrete_points);
    }
    
    std::cout << total_valid_sizes << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(M \log M \log N)$
- 离散化: 我们收集了 $2M$ 个点，排序去重需要 $O(M \log M)$ 的时间。
- 建树: 每条边需要插入到线段树中。线段树的高度是 $O(\log M)$ ，所以一次插入操作会把边放到 $O(\log M)$ 个节点上。总共有 $M$ 条边，所以建树过程的时间复杂度是 $O(M \log M)$ 。
- DFS遍历: DFS会遍历整个线段树。在树的每一层，每条边最多出现两次。树的深度是 $O(\log M)$ 。在每个节点，我们会对边进行 unite 操作。一次 unite 操作（包括 find_set）在使用按大小合并和路径压缩的并查集中，均摊时间复杂度是 $O(\alpha(N))$ ，但是我们为了撤销，使用的 find_set 是递归查找，没有做路径压缩，复杂度是 $O(\log N)$ 。因此，总的DFS时间复杂度是 $O(M \log M \cdot \log N)$ 。
- 综合起来，总时间复杂度由DFS部分主导，为 $O(M \log M \log N)$ 。
空间复杂度: $O(M \log M)$
- 离散化点: $O(M)$
- 线段树: 所有边在整棵树中总共会被存储 $O(M \log M)$ 次，这是空间占用的主要部分。
- 并查集历史记录: 在DFS过程中，历史记录栈的深度最多为 $O(M \log M)$ （虽然在任意时刻，栈的大小与DFS深度和节点边数有关，最坏情况下是 $O(M \log M)$ ），但由于DFS的回溯，实际同时存在的记录是 $O(\text{depth} \times \text{edges_per_node}) = O(\log M \cdot M)$ 。更精确地说是 $O(M \log N)$ ，因为并查集的高度是 $\log N$ 。总的来说，是 $O(M \log M)$ 。

知识点总结

这道题是一个非常经典的算法组合应用题，能解决它说明你很厉害了哦，喵~

问题转化: 核心思想是把对“无数个连续体型”的查询，转化为对“有限个离散区间”的查询。这是离散化的威力！
线段树分治: 当一个操作或一个条件在某个连续的“时间”或“坐标”区间上生效时，就可以考虑用线段树来管理这些区间。通过DFS遍历线段树，将区间问题转化为一系列在不同时间段内增删操作的问题。
可撤销并查集 (DSU with Rollback): 这是线段树分治的完美搭档！当我们需要在DFS的回溯过程中“撤销”数据结构的变化时，就需要这种支持回滚操作的数据结构。通过记录历史状态并恢复，我们能让并查集在分治的“时间线”上自由穿梭。

掌握了这些，以后遇到类似“在某个区间/时间段内查询图的连通性/属性”的问题，你就能一眼看穿啦！加油哦，探险家！喵~

Explorer - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

从暴力到优化，喵~ ​

线段树分治 + 可撤销并查集！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​