题解

涉及知识点

1. 并查集（Disjoint Set Union, DSU）

   • 用于动态维护已修复电脑的连通性。
   • 核心操作：
     • find(u)：查找 $u$ 的根节点。
     • union(u, v)：合并 $u$ 和 $v$ 所在集合。

2. 几何距离计算

   • 两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的欧氏距离：
     [ \text{distance} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} ]
   • 直接通信条件：$\text{distance} \leq d$。

3. 离线处理与在线查询

   • 修复操作（O p）实时更新连通性。
   • 测试操作（S p q）即时查询并查集。

代码（C++）

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

vector<int> parent;
vector<pair<int, int>> coords;
vector<bool> repaired;
int N, d;

int find(int u) {
    if (parent[u] != u) {
        parent[u] = find(parent[u]);
    }
    return parent[u];
}

void unite(int u, int v) {
    int pu = find(u), pv = find(v);
    if (pu != pv) {
        parent[pv] = pu;
    }
}

double distance(int i, int j) {
    double dx = coords[i].first - coords[j].first;
    double dy = coords[i].second - coords[j].second;
    return sqrt(dx * dx + dy * dy);
}

int main() {
    cin >> N >> d;
    coords.resize(N + 1);
    parent.resize(N + 1);
    repaired.assign(N + 1, false);
    for (int i = 1; i <= N; ++i) {
        cin >> coords[i].first >> coords[i].second;
        parent[i] = i;
    }

    string op;
    while (cin >> op) {
        if (op == "O") {
            int p;
            cin >> p;
            repaired[p] = true;
            for (int i = 1; i <= N; ++i) {
                if (i != p && repaired[i] && distance(i, p) <= d) {
                    unite(i, p);
                }
            }
        } else if (op == "S") {
            int p, q;
            cin >> p >> q;
            if (repaired[p] && repaired[q] && find(p) == find(q)) {
                cout << "SUCCESS\n";
            } else {
                cout << "FAIL\n";
            }
        }
    }
    return 0;
}

代码解释

1. 初始化：
   • 读取电脑坐标并初始化并查集。
2. 修复操作（O p）：
   • 标记电脑 $p$ 为已修复，并遍历所有其他已修复电脑，若距离 $\leq d$ 则合并集合。
3. 测试操作（S p q）：
   • 检查 $p$ 和 $q$ 是否均已修复且属于同一连通分量。

总结

本题通过并查集动态维护连通性，结合几何距离计算实现高效查询，适用于大规模实时网络修复场景。