题面
TT 写了一个长度为 N 的整数序列，但她不会直接告诉 FF 这个序列是什么。FF 会进行 M 次提问，每次提问会指定一个连续的子区间 [Ai, Bi]，TT 则回答这个区间的和是 Si。
然而，TT 为了“惩罚”FF，有时会故意说错答案。FF 也很聪明，他能检测出哪些回答与之前的回答是矛盾（不兼容）的。一旦发现某个回答是错误的，他在判断后续的回答时会忽略这个错误信息。
你的任务是：编写一个程序，根据这 M 次提问和回答，统计出其中有多少个回答是错误的。
输入格式
- 第一行包含两个整数
N和M，分别表示序列的长度和提问的次数。 - 接下来
M行，每行包含三个整数Ai,Bi和Si，表示一次提问和回答：区间[Ai, Bi]的和为Si。 - 数据保证
0 < Ai <= Bi <= N。
输出格式
输出一个整数，表示错误回答的总数。
样例输入
10 5
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1
样例输出
1
题解
关键在于如何利用 前缀和 思想，将 区间和 的关系转换为 并查集中节点之间 的关系。
- 核心思想：带权并查集。
- 关键转换：将闭区间
[a, b]转换为左闭右开区间(a-1, b]，从而利用前缀和原理。 - 权值定义：
v[x]代表节点x到其根节点的距离（区间和）。 - 冲突条件：当两个端点在同一集合时，通过权值差计算出的区间和与给出的值不一致。
- 合并公式：
v[fy] = s + v[x] - v[y];这个公式可以通过画向量图来加深理解。
代码实现
#include<bits/stdc++.h>
using namespace std;
int n,m,Fa[200002],v[200002];
int GetFa(int x) {if (x==Fa[x]) return x;int fx=Fa[x];Fa[x]=GetFa(Fa[x]);v[x]=v[x]+v[fx];return Fa[x];
}
int main(){while (scanf("%d%d",&n,&m)==2) {int ans=0;for (int i=0;i<=n;i++) Fa[i]=i;for (int i=0;i<=n;i++) v[i]=0;// 节点i到根节点r_i的区间和。(r_i,i]for (int i=1;i<=m;i++) {int x,y,z;cin>>x>>y>>z;int fx=GetFa(x-1),fy=GetFa(y);if (fx==fy) {if (v[y]-v[x-1]!=z) ans++;} else {Fa[fy]=fx,v[fy]=z+v[x-1]-v[y];}}cout<<ans<<endl;}return 0;
}