一、问题数学建模

1.1 问题本质

这是一个二维区间交集统计问题，核心在于高效计算大量区间对的交集大小之和。

数学形式化

给定：

• $n \times m$ 的棋盘
• $T$ 个线索（横向或纵向）
• 每个线索包含若干连续空格，每个空格可填 $1 \sim k$ 的数字
• 每个空格恰好属于一个横向线索和一个纵向线索

线索的候选数集合：对于长度为 $\text{len}$、目标和为 $s$ 的线索，其候选数集合 $C$ 满足：

$$C = \{x \mid x \in [1, k], \exists \text{满足约束的方案使得} x \text{出现}\} $$

空格的候选数：空格 $(i, j)$ 的候选数集合为：

$$S_{i,j} = C_{\text{row}(i,j)} \cap C_{\text{col}(i,j)} $$

目标：计算所有空格的候选数个数之和：

$$\text{答案} = \sum_{\text{所有空格}} |S_{i,j}|$$

---

1.2 朴素算法的瓶颈

直接枚举：

int ans = 0;
for (每个空格 (i, j)) {
    set<int> row_candidates = 计算行线索的候选数();
    set<int> col_candidates = 计算列线索的候选数();
    
    // 求交集
    set<int> intersection;
    set_intersection(row_candidates, col_candidates, ...);
    
    ans += intersection.size();
}

复杂度分析：

• 空格数量：$O(T)$（最多 $10^5$）
• 每次交集计算：$O(k)$（最多 $10^5$）
• 总复杂度：$O(T \times k) = O(10^{10})$ ❌ 超时

---

二、核心算法思想

2.1 关键观察：扫描线转化

二维问题 → 一维问题

将问题转化为：按列扫描，对于每一列的列线索，计算它与当前活跃的所有行线索的交集大小之和。

图示（以第 3 列为例）：

列扫描到第3列：
- 活跃的行线索：第2行(列2-3)、第3行(列2-3)、第4行(列2-6)
- 当前列的列线索：第3列(行2-5)

需要计算：
  列线索(第3列,行2-5) 与 行线索(第2行) 的交集
+ 列线索(第3列,行2-5) 与 行线索(第3行) 的交集
+ 列线索(第3列,行2-5) 与 行线索(第4行) 的交集

2.2 差分思想优化

行线索的生命周期：

• 第 $x$ 行，列 $[y_1, y_2]$ 的行线索
• 在列 $y_1$ 时"激活"
• 在列 $y_2 + 1$ 时"失效"

实现方式：

// 在列 y1 处记录：行线索加入
G[y1].push_back({候选数范围, 行号, +1});

// 在列 y2+1 处记录：行线索删除
G[y2+1].push_back({候选数范围, 行号, -1});

2.3 二维数据结构

问题转化为动态维护二维信息：

• 第一维：行号 $\in [1, n]$
• 第二维：候选数值 $\in [1, k]$

查询需求：给定行范围 $[r_1, r_2]$ 和值域范围 $[v_1, v_2]$，求矩形区域内的"权重和"

数据结构选择：

• 树状数组：维护行号维度（支持单点修改、前缀查询）
• 动态开点线段树：维护值域维度（支持区间修改、区间查询）

---

三、数学基础：候选数范围计算

3.1 可行性判断

对于长度 $\text{len}$、目标和 $s$，从 $[1, k]$ 中选 $\text{len}$ 个不重复数字。

边界计算：

$$\begin{aligned} \text{最小和} \quad lb &= 1 + 2 + \cdots + \text{len} = \frac{\text{len} \times (\text{len}+1)}{2} \\ \text{最大和} \quad rb &= k + (k-1) + \cdots + (k-\text{len}+1) = \frac{\text{len} \times (2k - \text{len}+1)}{2} \end{aligned} $$

可行性条件：

$$lb \le s \le rb$$

long long lb = 1LL * len * (len + 1) / 2;
long long rb = 1LL * len * (k + k - len + 1) / 2;

if (s < lb || s > rb) {
    return {-1, 0, 0};  // 无解
}

---

3.2 候选数边界推导

定理 1：最小候选数

命题：最小候选数 $l_{\min}$ 为能够与其他 $\text{len}-1$ 个数凑出和 $s$ 的最小值。

推导： 为了让 $l_{\min}$ 尽可能小，其他 $\text{len}-1$ 个数应尽可能大：

$$\{k, k-1, \ldots, k-\text{len}+2\}$$

这些数的和为：

$$\text{sum}_{\max} = \frac{(\text{len}-1) \times (2k - \text{len}+2)}{2} = rb - (k - \text{len}+1) $$

因此：

$$l_{\min} + \text{sum}_{\max} = s \implies l_{\min} = k - \text{len} + 1 + (s - rb) $$

但 $l_{\min} \ge 1$，所以：

$$l = \max(1, k - \text{len} + 1 + s - rb)$$

定理 2：最大候选数

推导（同理）：

$$r = \min(k, \text{len} + s - lb)$$

代码实现：

int l = max(1LL, k - len + 1 + s - rb);
int r = min(1LL * k, len + s - lb);

---

3.3 特殊情况：候选数范围中的"洞"

情况 1：长度为 2 的对称性

当 $\text{len} = 2$ 时，如果 $s$ 为偶数，则 $\frac{s}{2}$ 不能被选（会导致两数相同）。

示例：

• $\text{len} = 2, s = 6, k = 9$
• 可行方案：$(1,5), (2,4)$
• 候选数集合：$\{1, 2, 4, 5\}$
• $3$ 不在候选集（因为 $3+3=6$ 但违反不重复约束）

if (len == 2 && s % 2 == 0 && s / 2 <= k) {
    return {l, r, s/2};  // 第三个参数表示"洞"
}

情况 2：边界特判

当 $s = lb + 1$ 或 $s = rb - 1$ 时，候选数范围会出现特殊的洞：

if (s == lb + 1) {
    return {1, len+1, len};  // [1, len+1] 中 len 是洞
}

if (s == rb - 1) {
    return {k-len, k, k-len+1};  // [k-len, k] 中 k-len+1 是洞
}

情况 3：紧邻边界

当 $k = \text{len} + 1$ 且 $s \notin \{lb, rb\}$ 时：

$$\text{洞的位置} = k - \text{len} + rb - s$$

数学原理：此时只有一个数字不被选中，该数字可以通过总和计算得出。

---

四、算法流程详解

4.1 预处理阶段

步骤 1：计算候选数范围

struct Node {
    int l, r;    // 候选数范围 [l, r]
    int no;      // 范围内的"洞"（0表示无洞）
};

Node get_candidates(int len, long long s, int k) {
    // 计算 lb, rb
    long long lb = 1LL * len * (len + 1) / 2;
    long long rb = 1LL * len * (k + k - len + 1) / 2;
    
    // 可行性检查
    if (len > k || s < lb || s > rb) {
        return {-1, 0, 0};
    }
    
    // 计算边界
    int l = max(1LL, k - len + 1 + s - rb);
    int r = min(1LL * k, len + s - lb);
    
    // 特判"洞"
    if (s == lb + 1) return {1, len+1, len};
    if (s == rb - 1) return {k-len, k, k-len+1};
    if (k == len + 1 && s != lb && s != rb) {
        return {l, r, k - len + rb - s};
    }
    if (len == 2 && s % 2 == 0 && s / 2 <= k) {
        return {l, r, s/2};
    }
    
    return {l, r, 0};
}

步骤 2：线索分组

// 存储格式：(候选数范围, 行号/列号, 系数)
vector<pair<Node, int>> G[N];  // G[i]: 第 i 列的行线索事件
vector<pair<Node, int>> H[N];  // H[i]: 第 i 列的列线索查询

for (int i = 1; i <= T; i++) {
    int type, x, y1, y2;
    long long s;
    // 读入线索...
    
    Node cand = get_candidates(y2 - y1 + 1, s, k);
    
    if (type == 0) {  // 行线索
        G[y1].push_back({cand, x});      // 列 y1 处激活
        G[y2+1].push_back({cand, -x});   // 列 y2+1 处失效
    } else {  // 列线索
        // 查询行范围 [y1, y2] 拆成前缀差
        H[x].push_back({cand, y2});      // 前缀 [1, y2]
        H[x].push_back({cand, 1-y1});    // 减去前缀 [1, y1-1]
    }
}

---

4.2 动态开点线段树

数据结构定义

struct SegmentTree {
    long long sum[N * 40];   // 子树和
    int tag[N * 40];         // 懒标记
    int lson[N * 40];        // 左儿子编号
    int rson[N * 40];        // 右儿子编号
    int tot;                 // 节点计数器
    
    // 区间修改
    void update(int &v, int l, int r, int ql, int qr, int w);
    
    // 区间查询
    long long query(int v, int l, int r, int ql, int qr);
};

区间修改操作

void update(int &v, int l, int r, int ql, int qr, int w) {
    // 动态创建节点
    if (!v) v = ++tot;
    
    // 更新子树和（先于递归，因为包含本层贡献）
    int overlap = min(r, qr) - max(l, ql) + 1;
    sum[v] += 1LL * overlap * w;
    
    // 完全覆盖：打标记，不再递归
    if (ql <= l && r <= qr) {
        tag[v] += w;
        return;
    }
    
    // 部分覆盖：递归左右子树
    int mid = (l + r) >> 1;
    if (ql <= mid) update(lson[v], l, mid, ql, qr, w);
    if (qr > mid)  update(rson[v], mid+1, r, ql, qr, w);
}

关键点：

1. 动态开点：只在访问时创建节点，节省空间
2. 先更新 sum：每个节点的 sum 包含自己和子树的贡献
3. 懒标记下放时机：在完全覆盖时打标记，避免继续递归

区间查询操作

long long query(int v, int l, int r, int ql, int qr) {
    // 节点不存在
    if (!v) return 0;
    
    // 完全覆盖：直接返回子树和
    if (ql <= l && r <= qr) {
        return sum[v];
    }
    
    // 部分覆盖：递归查询 + 懒标记贡献
    int mid = (l + r) >> 1;
    long long res = 0;
    
    if (ql <= mid) res += query(lson[v], l, mid, ql, qr);
    if (qr > mid)  res += query(rson[v], mid+1, r, ql, qr);
    
    // 加上本节点懒标记对查询区间的贡献
    int overlap = min(r, qr) - max(l, ql) + 1;
    res += 1LL * tag[v] * overlap;
    
    return res;
}

---

4.3 树状数组

数据结构定义

struct BIT {
    int root[N];  // root[i]: 行号 i 对应的线段树根节点
    SegmentTree seg;
    
    // 单点修改（行号 x，候选数范围 cand，系数 coef）
    void insert(int x, Node cand, int coef);
    
    // 前缀查询（行号前缀 [1, x]，候选数范围 cand）
    long long query(int x, Node cand);
};

插入操作

void insert(int x, Node cand, int coef) {
    // 候选数范围无效
    if (cand.l < 0) return;
    
    // 树状数组向上更新
    for (; x <= n; x += x & -x) {
        // 给 [cand.l, cand.r] 区间 +coef
        seg.update(root[x], 1, k, cand.l, cand.r, coef);
        
        // 如果有洞，给洞的位置 -coef
        if (cand.no) {
            seg.update(root[x], 1, k, cand.no, cand.no, -coef);
        }
    }
}

含义：

• coef = +1：行线索激活
• coef = -1：行线索失效

树状数组原理：

• 更新位置 $x$ 时，同时更新所有包含 $x$ 的区间（即 $x, x + \text{lowbit}(x), \ldots$）
• 这样查询前缀和时，只需访问 $O(\log n)$ 个节点

查询操作

long long query(int x, Node cand) {
    // 候选数范围无效
    if (cand.l < 0) return 0;
    
    long long res = 0;
    
    // 树状数组向下累加
    for (; x > 0; x -= x & -x) {
        // 查询 [cand.l, cand.r] 区间和
        res += seg.query(root[x], 1, k, cand.l, cand.r);
        
        // 如果有洞，减去洞的贡献
        if (cand.no) {
            res -= seg.query(root[x], 1, k, cand.no, cand.no);
        }
    }
    
    return res;
}

---

4.4 扫描线主流程

long long ans = 0;
BIT bit;

for (int col = 1; col <= m; col++) {
    // 步骤 1：处理该列的行线索
    for (auto [cand, row_sign] : G[col]) {
        int row = abs(row_sign);
        int coef = (row_sign > 0) ? 1 : -1;
        bit.insert(row, cand, coef);
    }
    
    // 步骤 2：处理该列的列线索
    for (auto [cand, row_prefix] : H[col]) {
        int row = abs(row_prefix);
        int coef = (row_prefix > 0) ? 1 : -1;
        ans += bit.query(row, cand) * coef;
    }
}

cout << ans << endl;

流程图：

扫描第 col 列：
  ├─ 遍历 G[col]：更新行线索
  │   ├─ row_sign > 0：激活行线索（+1）
  │   └─ row_sign < 0：失效行线索（-1）
  │
  └─ 遍历 H[col]：查询列线索
      ├─ row_prefix > 0：查询 [1, row_prefix]（+1）
      └─ row_prefix < 0：查询 [1, |row_prefix|-1]（-1）

---

五、复杂度分析

时间复杂度

操作	单次复杂度	调用次数	总复杂度
计算候选数范围	$O(1)$	$T$	$O(T)$
树状数组插入	$O(\log n)$	$2T$	$O(T \log n)$
线段树区间修改	$O(\log k)$	$O(T \log n)$	$O(T \log n \log k)$
树状数组查询	$O(\log n)$	$2T$	$O(T \log n)$
线段树区间查询	$O(\log k)$	$O(T \log n)$	$O(T \log n \log k)$

总时间复杂度：$O(T \log n \log k)$

数值估算：

$$T \log n \log k \approx 10^5 \times 17 \times 17 \approx 3 \times 10^7 $$

空间复杂度

• 线段树节点数：每次修改/查询创建 $O(\log k)$ 个节点，共 $O(T \log n \log k)$ 个节点
• 树状数组：$O(n)$
• 其他辅助数组：$O(T)$

总空间复杂度：$O(T \log n \log k)$

---

六、数学理论基础

定理 3：候选数范围的完备性

命题：除特殊"洞"外，$[l, r]$ 内所有数字都可能出现在某个合法方案中。

证明要点： 对于 $x \in [l, r]$，构造方案：

1. 选择 $x$
2. 剩余 $\text{len}-1$ 个数从 $[1, k] \setminus \{x\}$ 中选择，使得和为 $s - x$

由于 $x \in [l, r]$，必然存在满足条件的选择方案。□

定理 4：树状数组的区间拆分

命题：查询区间 $[a, b]$ 可以拆分为 $\text{query}(b) - \text{query}(a-1)$。

证明：

$$\sum_{i=a}^{b} w_i = \sum_{i=1}^{b} w_i - \sum_{i=1}^{a-1} w_i $$

这是本题将列线索拆分为两个前缀查询的理论基础。□

---

七、算法优化技巧

优化 1：位运算优化

// 计算 lowbit
int lowbit(int x) {
    return x & -x;
}

// 树状数组更新
for (int i = x; i <= n; i += lowbit(i)) {
    // ...
}

优化 2：内存池优化

// 避免动态分配，预分配内存池
const int MAXNODES = 4000000;
struct SegmentTree {
    long long sum[MAXNODES];
    int tag[MAXNODES];
    int lson[MAXNODES], rson[MAXNODES];
    int tot = 0;
};

优化 3：常数优化

// 使用位运算计算中点
int mid = (l + r) >> 1;

// 使用快速读入
inline long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

---

八、易错点提醒

易错点 1：候选数范围的边界

// ❌ 错误：边界计算溢出
int l = k - len + 1 + s - rb;  // s 可能达到 10^18

// ✅ 正确：使用 long long
int l = max(1LL, k - len + 1 + s - rb);

易错点 2：洞的处理

// ❌ 错误：忘记处理洞
seg.update(root[x], 1, k, cand.l, cand.r, coef);

// ✅ 正确：检查并处理洞
seg.update(root[x], 1, k, cand.l, cand.r, coef);
if (cand.no) {
    seg.update(root[x], 1, k, cand.no, cand.no, -coef);
}

易错点 3：前缀查询的拆分

// ❌ 错误：直接查询区间 [y1, y2]
ans += bit.query(y2 - y1 + 1, cand);

// ✅ 正确：拆分成两个前缀
ans += bit.query(y2, cand);    // +前缀 [1, y2]
ans -= bit.query(y1-1, cand);  // -前缀 [1, y1-1]

易错点 4：动态开点的引用传递

// ❌ 错误：值传递，节点创建失败
void update(int v, int l, int r, ...) {
    if (!v) v = ++tot;  // v 只是局部变量
}

// ✅ 正确：引用传递
void update(int &v, int l, int r, ...) {
    if (!v) v = ++tot;  // 修改实际的 root[x]
}

---

九、关键数据结构总结

数据映射表

结构	含义	范围
Node{l, r, no}	候选数范围及洞	$l, r \in [1, k]$
G[col]	第 col 列的行线索事件	$\text{col} \in [1, m]$
H[col]	第 col 列的列线索查询
root[x]	行号 x 的线段树根	$x \in [1, n]$
seg.sum[v]	节点 v 的子树和	$v \in [1, \text{tot}]$

符号约定

符号	含义
$\text{len}$	线索包含的空格数
$s$	线索的目标和
$lb$	理论最小和
$rb$	理论最大和
$[l, r]$	候选数范围
$\text{no}$	候选数范围中的洞

---

十、算法框架

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

// ========== 第一部分：候选数范围计算 ==========
struct Node {
    int l, r, no;
};

Node get_candidates(int len, long long s, int k) {
    // ... 见 4.1 节
}

// ========== 第二部分：动态开点线段树 ==========
struct SegmentTree {
    // ... 见 4.2 节
};

// ========== 第三部分：树状数组 ==========
struct BIT {
    // ... 见 4.3 节
};

// ========== 第四部分：主函数 ==========
int main() {
    // 读入数据
    int n, m, k, T;
    cin >> n >> m >> k >> T;
    
    // 预处理：分组线索
    for (int i = 1; i <= T; i++) {
        // ... 见 4.1 节
    }
    
    // 扫描线
    long long ans = 0;
    BIT bit;
    for (int col = 1; col <= m; col++) {
        // ... 见 4.4 节
    }
    
    cout << ans << endl;
    return 0;
}

---

十一、相关知识点

前置知识

• ✅ 树状数组（Binary Indexed Tree）
• ✅ 线段树（Segment Tree）
• ✅ 扫描线算法（Sweep Line）
• ✅ 差分思想

进阶知识

• ✅ 动态开点线段树
• ✅ 二维数据结构
• ✅ 贪心算法（候选数边界计算）
• ✅ 组合数学（可行性分析）

相关题目

• 二维偏序问题
• 矩形面积并
• 区间交集统计

---

---

圣彼得堡桥梁问题 - 题解

一、问题数学建模

1.1 问题本质

这是一个带修改的动态图连通性问题，核心在于高效处理图结构的动态变化和连通性查询。

问题形式化

给定：

• $n$ 个岛屿（顶点），$m$ 座桥梁（边）
• 每座桥梁 $i$ 连接两个岛屿 $u_i$ 和 $v_i$，有重量限制 $d_i$
• $q$ 个操作序列

两种操作：

1. 修改操作：将桥梁 $b_j$ 的重量限制改为 $r_j$
2. 查询操作：重量为 $w_j$ 的汽车从岛屿 $s_j$ 出发，能到达多少个岛屿

可达性定义：汽车重量为 $w$，只能通过重量限制 $\ge w$ 的桥梁。岛屿 $u$ 和 $v$ 连通，当且仅当存在一条路径，使得路径上所有桥梁的重量限制都 $\ge w$。

目标：对于每个查询操作，计算从起点出发能到达的岛屿数量。

---

1.2 朴素算法的瓶颈

方法 1：暴力 BFS/DFS

// 对每个查询
for (每个查询 (s, w)) {
    // BFS/DFS 遍历所有满足条件的边
    visited[s] = true;
    queue<int> q;
    q.push(s);
    int count = 1;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (边 (u, v) 的重量限制 d) {
            if (d >= w && !visited[v]) {
                visited[v] = true;
                q.push(v);
                count++;
            }
        }
    }
    
    输出 count;
}

复杂度分析：

• 每次查询：$O(n + m)$
• 总复杂度：$O(q \times (n + m)) \approx 10^5 \times 10^5 = 10^{10}$ ❌ 超时

方法 2：预处理所有边权的并查集

预先对每个可能的权值建立并查集状态，但由于权值范围达到 $10^9$，空间和时间都不可行。

---

二、核心算法思想

2.1 关键观察一：离线查询 + Kruskal 思想

观察：如果没有修改操作，可以用类似 Kruskal 的思路高效处理查询。

离线处理策略

1. 边排序：将所有桥梁按重量限制从大到小排序
2. 查询排序：将所有查询按汽车重量从大到小排序
3. 双指针扫描：
   • 维护一个并查集
   • 对于当前查询的重量 $w$，将所有重量限制 $\ge w$ 的边加入并查集
   • 查询起点所在连通块的大小

// 无修改时的离线算法框架
sort(edges, cmp_by_weight_desc);  // 边按权值降序
sort(queries, cmp_by_weight_desc); // 查询按权值降序

int edge_ptr = 0;
for (每个查询 q: 重量 w, 起点 s) {
    // 加入所有权值 >= w 的边
    while (edge_ptr < m && edges[edge_ptr].weight >= w) {
        merge(edges[edge_ptr].u, edges[edge_ptr].v);
        edge_ptr++;
    }
    
    // 查询连通块大小
    ans[q.id] = size[find(s)];
}

复杂度：$O((m + q) \log (m + q) + m \alpha(n))$，其中 $\alpha$ 是反阿克曼函数。

---

2.2 关键观察二：操作序列分块

问题：有修改操作时，边权会动态变化，无法直接离线处理。

解决方案：将操作序列分块，每 $B$ 个操作为一块。

分块思想

对于每一块操作：

1. 提取查询：记录该块中的所有查询操作
2. 离线处理：对该块的查询进行离线求解
3. 应用修改：块结束后，将所有修改操作应用到原始数据
4. 进入下一块：重复上述过程

B = 1200;  // 块大小
for (int i = 1; i <= Q; i++) {
    读入操作 i;
    
    if (操作类型 == 修改) {
        记录修改到 q1[];
    } else {
        记录查询到 q2[];
    }
    
    // 块结束或操作序列结束
    if (i % B == 0 || i == Q) {
        solve();  // 处理当前块
        清空 q1[], q2[];
    }
}

---

2.3 关键观察三：边的分类处理

对于每个查询，需要考虑的边分为三类：

类型 1：不受当前块修改影响的边

这些边在整个块中都保持原始权值，可以直接按权值加入并查集。

// 标记块内被修改的边
for (int i = 1; i <= c1; i++)
    flag[loc[q1[i].x]] = true;  // q1[i].x 是被修改的桥梁编号

// 加入未被修改的边
for (边 e: 按权值降序) {
    if (!flag[e.id] && e.weight >= query_weight) {
        merge(e.u, e.v);
    }
}

类型 2：查询前被修改的边

对于查询 $q$，在时间 $t_q$ 之前被修改过的边，应使用最后一次修改后的权值。

重要细节：同一条边可能被修改多次，只有最后一次修改有效。

// 处理查询前的修改
for (int j = 1; j <= now; j++) {  // now: 查询前的修改数量
    if (!app[q1[j].bridge_id]) {  // 该边还未处理
        app[q1[j].bridge_id] = true;
        if (q1[j].new_weight >= query_weight) {
            merge(bridge.u, bridge.v);
        }
    }
}

类型 3：查询后才修改的边

这些边应使用原始权值（因为修改发生在查询之后）。

// 处理查询后的修改
for (int j = now + 1; j <= c1; j++) {
    if (!app[q1[j].bridge_id]) {
        app[q1[j].bridge_id] = true;
        if (original_weight >= query_weight) {
            merge(bridge.u, bridge.v);
        }
    }
}

---

2.4 关键观察四：可撤销并查集

问题：每个查询需要独立计算，查询之间不能相互影响。

解决方案：使用可撤销并查集，查询完成后回滚状态。

可撤销并查集原理

核心思想：

1. 禁用路径压缩：使用按秩合并，但不进行路径压缩（因为路径压缩难以撤销）
2. 记录合并历史：用栈记录每次合并的操作
3. 回滚操作：查询后，按栈的逆序撤销合并

stack<pair<int, int>> st;  // 记录 (父节点, 子节点)

// 合并操作（不路径压缩）
int find(int x) {
    return x == fa[x] ? x : find(fa[x]);  // 不修改 fa[x]
}

void merge(int x, int y, bool need_rollback) {
    int fx = find(x), fy = find(y);
    
    if (fx != fy) {
        // 按秩合并：小树合并到大树
        if (siz[fx] < siz[fy]) swap(fx, fy);
        
        fa[fy] = fx;
        siz[fx] += siz[fy];
        
        // 记录合并操作
        if (need_rollback) {
            st.push({fx, fy});
        }
    }
}

// 回滚操作
while (!st.empty()) {
    auto [x, y] = st.top();
    st.pop();
    
    // 撤销合并
    fa[y] = y;
    siz[x] -= siz[y];
}

复杂度：每次合并和回滚均为 $O(\log n)$。

---

三、算法流程详解

3.1 预处理阶段

模块 1：数据结构定义

const int N = 5e4 + 10, M = 1e5 + 10;

// 边的信息
struct edge {
    int x, y;    // 连接的两个岛屿
    int z;       // 重量限制
    int id;      // 边的编号（1 到 m）
} e[M];

// 查询信息
struct query {
    int x;       // 对于修改：桥梁编号；对于查询：起点岛屿
    int y;       // 对于修改：新权值；对于查询：汽车重量
    int id;      // 操作的时间戳
} q1[N], q2[N];  // q1: 修改操作，q2: 查询操作

// 并查集
int fa[N], siz[N];

// 辅助数组
int loc[M];      // loc[i]: 边 i 在排序后的位置
bool flag[M];    // flag[i]: 边 i 是否在当前块被修改
bool app[M];     // app[i]: 边 i 是否已被处理（去重）
int ans[M];      // ans[i]: 操作 i 的答案

模块 2：排序比较函数

// 边按权值降序排序
bool cmp(edge a, edge b) {
    return a.z > b.z;
}

// 查询按汽车重量降序排序
bool cmp2(query a, query b) {
    return a.y > b.y;
}

---

3.2 分块处理主流程

模块 3：solve 函数框架

void solve() {
    // 步骤 1: 排序
    sort(e + 1, e + 1 + m, cmp);      // 边按权值降序
    sort(q2 + 1, q2 + 1 + c2, cmp2);  // 查询按权值降序
    
    // 步骤 2: 预处理
    建立边编号到排序位置的映射();
    标记被修改的边();
    初始化并查集();
    
    // 步骤 3: 处理每个查询
    for (int i = 1; i <= c2; i++) {
        加入权值足够大的未修改边();
        处理块内修改的边();
        记录查询答案();
        回滚并查集();
        清空标记数组();
    }
    
    // 步骤 4: 应用块内所有修改
    for (int i = 1; i <= c1; i++)
        e[loc[q1[i].x]].z = q1[i].y;
}

---

3.3 查询处理详细流程

模块 4：边的添加策略

// 建立映射和标记
for (int i = 1; i <= m; i++) {
    loc[e[i].id] = i;  // 边 e[i].id 在排序后是第 i 条边
    flag[i] = false;
}

for (int i = 1; i <= c1; i++) {
    flag[loc[q1[i].x]] = true;  // 标记被修改的边
}

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

模块 5：双指针加边

int lst = 1;  // 边的指针

for (int i = 1; i <= c2; i++) {  // 从大到小处理查询
    // 加入所有权值 >= q2[i].y 的未修改边
    while (lst <= m && e[lst].z >= q2[i].y) {
        if (!flag[lst]) {
            merge(e[lst].x, e[lst].y, false);  // 永久合并，不需回滚
        }
        lst++;
    }
    
    // 处理被修改的边...
}

关键点：

• lst 只增不减，每条边最多访问一次
• 未被修改的边直接永久合并（need_rollback = false）

---

3.4 修改操作的时序处理

模块 6：确定查询的时间位置

// 统计查询前有多少个修改操作
int now = 0;
while (now < c1 && q1[now + 1].id <= q2[i].id) {
    now++;
}

含义：

• q1[1..now]：查询前的修改（使用新权值）
• q1[now+1..c1]：查询后的修改（使用原权值）

模块 7：处理查询前的修改

for (int j = now; j >= 1; j--) {
    if (!app[q1[j].x]) {  // 去重：只处理第一次遇到的边
        app[q1[j].x] = true;
        int num = loc[q1[j].x];  // 边在排序后的位置
        
        // 使用修改后的权值
        if (q1[j].y >= q2[i].y) {
            merge(e[num].x, e[num].y, true);  // 可撤销合并
        }
    }
}

关键点：

• 倒序遍历，遇到的第一次修改就是"最后一次修改"
• 合并操作可撤销（need_rollback = true）

模块 8：处理查询后的修改

for (int j = now + 1; j <= c1; j++) {
    if (!app[q1[j].x]) {
        app[q1[j].x] = true;
        int num = loc[q1[j].x];
        
        // 使用原始权值
        if (e[num].z >= q2[i].y) {
            merge(e[num].x, e[num].y, true);
        }
    }
}

---

3.5 查询答案与状态回滚

模块 9：记录答案并回滚

// 记录答案
ans[q2[i].id] = siz[find(q2[i].x)];

// 回滚可撤销合并
while (!st.empty()) {
    int x = st.top().first;
    int y = st.top().second;
    st.pop();
    
    // 确保 y 是子节点
    if (fa[x] == y) swap(x, y);
    
    // 撤销合并
    fa[y] = y;
    siz[x] -= siz[y];
}

// 清空去重标记
for (int j = 1; j <= c1; j++) {
    app[q1[j].x] = false;
}

关键细节：

• fa[x] == y 时需要交换：栈中记录的是 (大树根, 小树根)，但实际合并时是 fa[小树] = 大树
• 每个查询后必须清空 app 数组，保证下个查询独立

---

3.6 主函数流程

模块 10：输入与分块

int main() {
    scanf("%d%d", &n, &m);
    
    // 读入边
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
        e[i].id = i;
    }
    
    scanf("%d", &Q);
    B = 1200;  // 块大小
    
    int c1 = 0, c2 = 0;  // 当前块的修改/查询数量
    
    for (int i = 1; i <= Q; i++) {
        int t;
        scanf("%d", &t);
        ans[i] = -1;  // 标记为未处理
        
        if (t == 1) {  // 修改操作
            c1++;
            scanf("%d%d", &q1[c1].x, &q1[c1].y);
            q1[c1].id = i;
        } else {  // 查询操作
            c2++;
            scanf("%d%d", &q2[c2].x, &q2[c2].y);
            q2[c2].id = i;
        }
        
        // 块结束或操作序列结束
        if (i % B == 0 || i == Q) {
            solve();
            c1 = c2 = 0;  // 重置计数器
        }
    }
    
    // 输出所有查询答案
    for (int i = 1; i <= Q; i++) {
        if (ans[i] != -1) {
            printf("%d\n", ans[i]);
        }
    }
    
    return 0;
}

---

四、复杂度分析

4.1 时间复杂度

设操作序列被分成 $\frac{Q}{B}$ 块。

每块的复杂度

步骤	操作	单次复杂度	次数	总复杂度
排序边	sort(e, ...)	$O(m \log m)$	每块 1 次	$O(m \log m)$
排序查询	sort(q2, ...)	$O(B \log B)$		$O(B \log B)$
加未修改边	并查集合并	$O(\log n)$	最多 $m$ 次	$O(m \log n)$
处理修改边	并查集合并/回滚		每查询 $O(B)$ 次	$O(B^2 \log n)$

每块总复杂度：$O(m \log m + B^2 \log n)$

所有块总复杂度：

$$O\left(\frac{Q}{B} \times (m \log m + B^2 \log n)\right) = O\left(\frac{Qm \log m}{B} + QB \log n\right) $$

最优块大小

令 $\frac{Qm}{B} = QB$，得 $B = \sqrt{m}$。

当 $B \approx 1200 \approx \sqrt{m}$ 时，总复杂度为：

$$O(Q\sqrt{m} \log n + Q\sqrt{m} \log m) = O(Q\sqrt{m} \log m) $$

数值估算：

$$10^5 \times \sqrt{10^5} \times 17 \approx 5 \times 10^7 $$

4.2 空间复杂度

数组	大小	说明
e[]	$O(m)$	边的信息
q1[], q2[]	$O(B)$	每块的操作
fa[], siz[]	$O(n)$	并查集
loc[], flag[], app[]	$O(m)$	辅助数组
st	$O(B^2)$	最坏情况栈深度

总空间复杂度：$O(n + m + B^2) \approx O(n + m)$

---

五、算法优化技巧

优化 1：块大小的选择

// 理论最优：B = sqrt(m)
B = (int)sqrt(m) + 1;

// 实践中常用固定值（避免浮点运算）
B = 1200;  // 当 m ≈ 10^5 时

优化 2：并查集优化

// 按秩合并：始终将小树合并到大树
if (siz[fx] < siz[fy]) swap(fx, fy);
fa[fy] = fx;
siz[fx] += siz[fy];

效果：树的高度保持在 $O(\log n)$，保证 find 操作的效率。

优化 3：去重优化

// 使用布尔数组而非 set
bool app[M];

// 每次查询后批量清空，而非逐个清空
for (int j = 1; j <= c1; j++)
    app[q1[j].x] = false;

优化 4：栈的撤销顺序

// 确保撤销顺序正确
if (fa[x] == y) swap(x, y);  // y 必须是子节点
fa[y] = y;
siz[x] -= siz[y];

---

六、易错点提醒

易错点 1：find 函数的路径压缩

// ❌ 错误：使用路径压缩（无法撤销）
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

// ✅ 正确：不使用路径压缩
int find(int x) {
    return fa[x] == x ? x : find(fa[x]);
}

易错点 2：修改操作的去重

// ❌ 错误：未去重，同一条边被处理多次
for (int j = now; j >= 1; j--) {
    if (q1[j].y >= q2[i].y) {
        merge(...);  // 可能重复合并
    }
}

// ✅ 正确：使用 app 数组去重
for (int j = now; j >= 1; j--) {
    if (!app[q1[j].x]) {
        app[q1[j].x] = true;
        // 处理...
    }
}

易错点 3：查询时间的判断

// ❌ 错误：混淆查询前后的修改
int now = c1;  // 错误地认为所有修改都在查询前

// ✅ 正确：根据时间戳判断
int now = 0;
while (now < c1 && q1[now + 1].id <= q2[i].id) {
    now++;
}

易错点 4：回滚时的父子关系

// ❌ 错误：未判断父子关系
fa[y] = y;
siz[x] -= siz[y];  // 如果 x 不是 y 的父节点，会出错

// ✅ 正确：确保 y 是子节点
if (fa[x] == y) swap(x, y);
fa[y] = y;
siz[x] -= siz[y];

易错点 5：块结束后的状态更新

// ❌ 错误：忘记应用修改
solve();
c1 = c2 = 0;  // 仅重置计数器

// ✅ 正确：在 solve() 末尾应用修改
for (int i = 1; i <= c1; i++)
    e[loc[q1[i].x]].z = q1[i].y;

---

七、算法设计思想总结

7.1 分块思想的应用

核心理念：将操作序列分块，平衡在线与离线的优势。

• 在线优势：能实时处理修改
• 离线优势：能排序优化查询

分块的意义：

• 每 $B$ 个操作为一块，块内离线处理
• 块间维护数据结构的一致性

7.2 时序分离策略

问题：修改和查询交替出现，如何正确处理边权的时效性？

解决方案：

1. 查询前的修改：使用修改后的权值
2. 查询后的修改：使用原始权值
3. 去重处理：同一条边多次修改，只取最后一次

7.3 可撤销数据结构

核心技术：

• 操作记录：用栈记录所有可撤销操作
• 状态恢复：按栈的逆序恢复
• 限制条件：不能使用路径压缩等优化

适用场景：

• 需要多次独立查询
• 查询之间状态不共享
• 操作可以分解为"合并"和"撤销"