D - How Many Answers Are Wrong （带权并查集）

题目链接：https://vjudge.net/contest/339425#problem/D

给出一个区间的长度 N，及 M 个子区间和，形如：x y z, 表示
子区间 [x, y] 的和为 z
如果一个“子区间和”与前面的“子区间和”冲突，即为错误（而且这个“子区间和”将在接下来的判断中被忽略）。
求总错误个数。

Input

有多组数据。

每组数据第一行两个整数N M (1 <= N <= 200000, 1 <= M <= 40000),
接下来每行有 M 对关系 x y z;
注：可以认为 z 为32位整型。

Output

错误个数。

Sample Input

10 5
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1

Sample Output

假设我们给了【1，4】区间是 20 【3，4】区间是 15 ，再给你【1，2】区间是 30

很明显我们都知道这个【1，2】区间有问题

因为使用的都是闭区间，闭区间会加上端点值。这就提醒我们在处理闭区间的时候把一端变成开区间。

得到下面这个图 👇

我们再看什么时候一个区间的值可以由之前的区间值得出来呢？

很明显我们知道绿色边的区间值是可以求出来的，而红色边的区间值是无法求出来的。原因也很简单：0 和 2 在同一个并查集，而 0 和 3 不在同一个并查集

所以本题的求解思路：

如果给定区间的两个端点在同一个并查集我们就看给出的值和我们推断的值等不等

如果给定区间的两个端点不在同一个并查集我们就把它们合并

sum[roota] = -sum[a] + v + sum[b] （其实就是向量之间的关系）

 1 #include <math.h>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <string>
 7 #include <string.h>
 8 #include <vector>
 9 #include <map>
10 #include <stack>
11 #include <set>
12 //#include <random>
13 
14 #define LL long long
15 #define INF 0x3f3f3f3f
16 #define ls nod<<1
17 #define rs (nod<<1)+1
18 const int maxn = 3e5 + 10;
19 const double eps = 1e-9;
20 int pre[maxn],sum[maxn];
21 
22 void init(int n) {
23     for (int i=0;i<=n;i++) {
24         pre[i] = i;
25         sum[i] = 0;
26     }
27 }
28 
29 int find(int x) {
30     if (pre[x] != x) {
31         int t = pre[x];
32         pre[x] = find(pre[x]);
33         sum[x] += sum[t];
34     }
35     return pre[x];
36 }
37 
38 void merge(int x,int y) {
39     int rootx = find(x),rooty = find(y);
40     pre[rooty] = rootx;
41 }
42 int main() {
43     //freopen("../in.txt","r",stdin);
44     int n,m;
45     while (~scanf("%d%d",&n,&m)) {
46         init(n);
47         int ans = 0;
48         while (m--) {
49             int l,r,a;
50             scanf("%d%d%d",&l,&r,&a);
51             l--;
52             int rootl = find(l),rootr = find(r);
53             if (rootl == rootr) {
54                 if (sum[l]-sum[r] != a) {
55                     ans++;
56                 }
57             }
58             else {
59                 pre[rootl] = pre[rootr];
60                 sum[rootl] = sum[r] - sum[l] + a;
61             }
62         }
63         printf("%d\n",ans);
64     }
65     return 0;
66 }