小奇的骑行路线查询问题题解

一、题目核心分析

本题本质是区间道路连通性查询：第 $i$ 条道路仅在第 $i$ 天开放，需判断在 $[l, r]$ 区间内的道路构成的图中，城市 $s$ 与 $t$ 是否连通（小奇可在 $[l, r]$ 任意天数使用开放道路移动）。

关键约束决定算法方向：

• 城市数 $n \leq 1000$（规模小，适合并查集复制操作）；
• 道路数 $m$ 和查询数 $q$ 均达 $2 \times 10^5$（暴力遍历超时，需分块优化）。

核心思路：用分块将大区间拆分为“零散块+完整块”，结合并查集（DSU） 预处理完整块的连通状态，查询时仅需合并零散块与复用完整块结果，平衡预处理与查询效率。

二、算法原理：分块+并查集

1. 分块设计

将 $m$ 条道路按顺序分成 $B$ 块（块大小取 $B = \sqrt{m} \approx 450$，兼顾预处理和查询速度），总块数 $K = \lceil m/B \rceil$。任意查询区间 $[l, r]$ 可拆分为三部分：

• 左零散块：$l$ 所在块中从 $l$ 到块尾的道路；
• 中间完整块：$l$ 下一块到 $r$ 上一块的所有完整块；
• 右零散块：$r$ 所在块中从块头到 $r$ 的道路。

2. 并查集的三大作用

并查集是维护连通性的高效数据结构，本题需三种并查集：

1. 前缀并查集 pre[K+2]：pre[k] 存储前 $k$ 个完整块的连通状态（包含第 $1$ 到 $k \times B$ 条道路），预处理时按块顺序合并道路。
2. 后缀并查集 suf[K+2]：suf[k] 存储第 $k$ 个完整块到最后一条道路的连通状态（包含第 $(k-1) \times B + 1$ 到 $m$ 条道路），预处理时按块逆序合并道路。
3. 临时并查集：查询时临时合并“左零散块+中间完整块+右零散块”的道路，判断 $s$ 与 $t$ 连通性，查询后销毁不影响其他用例。

三、具体实现步骤

1. 预处理：构建前缀与后缀并查集

（1）前缀并查集 pre 构建

• 初始化 pre[0]：所有城市独立（父节点为自身，秩为 $1$）。
• 对每个块 $k$（1~K）：
  1. 复制 pre[k-1] 的 parent 和 rank 数组，作为 pre[k] 的初始状态；
  2. 合并第 $(k-1) \times B + 1$ 到 $\min(k \times B, m)$ 条道路，更新 pre[k] 的连通状态。

（2）后缀并查集 suf 构建

• 初始化 suf[K+1]：所有城市独立。
• 对每个块 $k$（K~1）：
  1. 复制 suf[k+1] 的 parent 和 rank 数组，作为 suf[k] 的初始状态；
  2. 合并第 $(k-1) \times B + 1$ 到 $\min(k \times B, m)$ 条道路，更新 suf[k] 的连通状态。

2. 处理查询：拆分区间+临时合并

对每个查询 $(l, r, s, t)$：

1. 特殊情况：若 $s == t$，直接输出 Yes（题目虽限定 $s \neq t$，但代码兼容避免异常）。
2. 块号计算：将道路索引转为 1-based 后，计算 $l$ 所在块 $L = (l-1)/B + 1$，$r$ 所在块 $R = (r-1)/B + 1$。
3. 区间合并与连通性判断：
   • 若 $L == R$（同一块）：初始化临时并查集，合并第 $l$ 到 $r$ 条道路，判断 $s$ 与 $t$ 是否连通。
   • 若 $L < R$（跨多块）：
     1. 初始化临时并查集为 pre[R-1]（复用中间完整块的连通状态）；
     2. 合并左零散块（第 $l$ 到 $L \times B$ 条道路）；
     3. 合并右零散块（第 $(R-1) \times B + 1$ 到 $r$ 条道路）；
     4. 查询临时并查集中 $s$ 与 $t$ 的根节点，相同则输出 Yes，否则 No。

四、C++ 代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;

const int MAXN = 1010;  // 城市数n≤1000
const int MAXM = 2e5 + 10;  // 道路数m≤2e5

// 并查集结构：存储parent和rank数组，支持复制
struct DSU {
    int parent[MAXN];
    int rank[MAXN];
    
    // 初始化：每个城市父节点为自身，秩为1
    void init() {
        for (int i = 1; i < MAXN; ++i) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    
    // 查找根节点（路径压缩）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // 合并两个集合（按秩合并）
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
    }
    
    // 复制另一个DSU的状态
    void copy(const DSU& other) {
        for (int i = 1; i < MAXN; ++i) {
            parent[i] = other.parent[i];
            rank[i] = other.rank[i];
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    // 存储道路：roads[i]是第i条道路的两个城市（1-based）
    vector<pair<int, int>> roads(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> roads[i].first >> roads[i].second;
    }
    
    // 分块参数：块大小B，总块数K
    int B = sqrt(m) + 1;
    int K = (m + B - 1) / B;  // 向上取整
    
    // 1. 预处理前缀并查集pre：pre[k]表示前k个完整块的连通状态
    vector<DSU> pre(K + 2);
    pre[0].init();  // 前0个块：所有城市独立
    for (int k = 1; k <= K; ++k) {
        pre[k].copy(pre[k - 1]);  // 继承前k-1块的状态
        // 当前块的道路范围：[start, end]（1-based）
        int start = (k - 1) * B + 1;
        int end = min(k * B, m);
        for (int i = start; i <= end; ++i) {
            int u = roads[i].first;
            int v = roads[i].second;
            pre[k].unite(u, v);
        }
    }
    
    // 2. 预处理后缀并查集suf：suf[k]表示第k个完整块到最后的连通状态
    vector<DSU> suf(K + 2);
    suf[K + 1].init();  // 第K+1个块：所有城市独立
    for (int k = K; k >= 1; --k) {
        suf[k].copy(suf[k + 1]);  // 继承k+1块的状态
        // 当前块的道路范围：[start, end]（1-based）
        int start = (k - 1) * B + 1;
        int end = min(k * B, m);
        for (int i = start; i <= end; ++i) {
            int u = roads[i].first;
            int v = roads[i].second;
            suf[k].unite(u, v);
        }
    }
    
    // 3. 处理每个查询
    while (q--) {
        int l, r, s, t;
        cin >> l >> r >> s >> t;
        
        if (s == t) {
            cout << "Yes\n";
            continue;
        }
        
        // 计算l和r所在的块（1-based块号）
        int L = (l - 1) / B + 1;
        int R = (r - 1) / B + 1;
        
        DSU tmp;
        if (L == R) {
            // 情况1：查询区间在同一个块内，直接合并l~r的道路
            tmp.init();
            for (int i = l; i <= r; ++i) {
                int u = roads[i].first;
                int v = roads[i].second;
                tmp.unite(u, v);
            }
        } else {
            // 情况2：查询区间跨块，合并左零散块+中间完整块+右零散块
            tmp.copy(pre[R - 1]);  // 先复制中间完整块（前R-1个块）的状态
            
            // 合并左零散块：l ~ L*B
            int left_end = L * B;
            for (int i = l; i <= left_end; ++i) {
                int u = roads[i].first;
                int v = roads[i].second;
                tmp.unite(u, v);
            }
            
            // 合并右零散块：(R-1)*B + 1 ~ r
            int right_start = (R - 1) * B + 1;
            for (int i = right_start; i <= r; ++i) {
                int u = roads[i].first;
                int v = roads[i].second;
                tmp.unite(u, v);
            }
        }
        
        // 判断s和t是否连通
        if (tmp.find(s) == tmp.find(t)) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    
    return 0;
}

五、关键细节与优化

1. 并查集复制效率：因 $n \leq 1000$，copy 函数仅需遍历 $1000$ 个元素，时间成本可忽略，是算法可行的核心前提。
2. 块大小选择：$B = \sqrt{m} \approx 450$ 是理论最优值——过小会增加完整块数量（预处理时间变长），过大则增加零散块合并时间（查询时间变长）。
3. 输入输出优化：C++ 中用 ios::sync_with_stdio(false); cin.tie(0); 关闭同步，避免大量查询导致的输入超时。

六、时间复杂度分析

• 预处理时间：前缀和后缀并查集各需合并 $m$ 条道路，每条合并操作时间为 $\alpha(n)$（并查集阿克曼函数，近似常数），总预处理时间 $O(m \alpha(n))$。
• 查询时间：单次查询最多合并 $2B$ 条零散道路，总查询时间 $O(q B \alpha(n))$。取 $B = \sqrt{m}$，总时间复杂度为 $O((m + q\sqrt{m}) \alpha(n))$，对 $m, q \leq 2 \times 10^5$ 完全适配。