区间带边权并查集，XY4060泄露的测试点

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

 

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

码蹄集

---

 

二、解题报告

1、思路分析

关于带边权并查集：并查集，扩展域并查集，带边权并查集详解，OJ练习，详细代码-CSDN博客

sum(a[l, r]) = x 转化为 S[r] - S[l - 1] = x

其中S[i] = sum(a[1...i])，规定 S[0] = 0

考虑 带边权并查集维护 信息

f[i] 为 i 的父节点，d[i] 为 S[i] - S[f[i]]

对于find(x) 操作，如果 f[x] = x，那么直接返回x

否则递归查询 find(f[x])，回溯时 把d[x] 和 d[f[x]] 合并，即 d[x] += d[f[x]]

对于 [l, r, x]，考虑如下情况：

l 和 r在同一集合，如果 d[l] - d[r] != x，说明无解

不在同一集合，取 fl 为 l所在集合的根节点，fr 为 r 所在集合根节点

那么考虑 fl 往 fr上合并，我们只需计算出 合并后的d[fl]

显然有 d[fl] = d[r] - d[l] - x

（因为 d[r] = S[r] - S[fr], d[l] = S[l] - S[fl], S[r] - S[l] = x)

处理完n条信息后，如果有合法解，那么0~m的根节点应该一样

此时S[i] = d[i] - d[0]

计算完S[i]后，可以根据 S[i] - S[i - 1] 计算原数组的值

2、复杂度

时间复杂度： O(NlogM)空间复杂度：O(M)

 

3、代码详解

#include <bits/stdc++.h>
using i64 = long long;int main() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);int n, m;std::cin >> n >> m;std::vector<int> f(m + 1);std::vector<i64> d(m + 1, 0);std::iota(f.begin(), f.end(), 0);auto find = [&](auto &&self, int x) -> int {if (f[x] == x) return x;int px = self(self, f[x]);d[x] += d[f[x]];return f[x] = px;};for (int i = 0; i < n; ++ i) {int l, r, x;std::cin >> l >> r >> x;-- l;int fl = find(find, l);int fr = find(find, r);if (fl == fr) {if (d[r] - d[l] != x) {std::cout << "ovo\n";return 0;}} else {i64 s = d[r] - d[l] - x;f[fl] = fr;d[fl] = s;}}std::vector<int> S(n + 1);int top = find(find, 0);for (int i = 0; i <= m; ++ i) {if (find(find, i) != top) {std::cout << "ovo\n";return 0;}S[i] = d[i] - d[0];}for (int i = 1; i <= m; ++ i) {std::cout << S[i] - S[i - 1] << " \n"[i == m];}return 0;
}