HDU 3038 How Many Answers Are Wrong：帶權並查集解決區間和矛盾檢測

題目大意

給定 n 次詢問，每次提供區間 [a, b] 的總和 c。需要判斷這 n 次給出的總和中，有多少次與前面已知的信息產生矛盾。

核心思路：帶權並查集

定義 sum[x] 表示從節點 x 到其所在集合根節點的距離（或權值和）。若區間 [a, b] 的總和為 c，則可轉化為：

sum[a] - sum[b+1] = c

這將問題轉化為維护節點之間的差值關係。使用並查集管理連通分量，並在 find 操作中進行路徑壓縮與權值更新：

• find(x) 返回 x 的根節點，同時將 sum[x] 更新為 x 到根節點的累積權值。
• 合併兩個集合時，根據已知關係 sum[a] - sum[b+1] = c 計算新的父子關係權值。

關鍵代碼實現（C++）

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 200010;
int fa[MAXN], sum[MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    int t = fa[x];
    fa[x] = find(fa[x]);
    sum[x] += sum[t]; // 路徑壓縮時累加權值
    return fa[x];
}

void unite(int x, int y, int a, int b, int c) {
    // 將 x 的根連接到 y 的根，並設置權值使關係成立
    if (x > y) {
        fa[y] = x;
        sum[y] = sum[a] - sum[b] - c;
    } else {
        fa[x] = y;
        sum[x] = sum[b] - sum[a] + c;
    }
}

int main() {
    int len, n;
    while (cin >> len >> n) {
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i <= 200001; ++i) fa[i] = i;
        int ans = 0;
        while (n--) {
            int a, b, c;
            cin >> a >> b >> c;
            ++b; // 轉為 [a, b+1) 區間
            int x = find(a), y = find(b);
            if (x == y) {
                if (sum[a] != sum[b] + c) ++ans; // 矛盾
            } else {
                unite(x, y, a, b, c);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度分析

並查集的路徑壓縮使得單次操作近似 O(α(n))，總時間複雜度 O(n α(n))，空間 O(N)，完全滿足題目限制。