http://acm.hdu.edu.cn/showproblem.php?pid=3038
大致题意：
有一个区间[0,n]，然后会给出你m个区间和，每次给出a，b，v，表示区间[a,b]的区间和为v，但每次给出的区间可能与之前的有冲突，问这样起冲突的区间共有多少个
首先区间[a,b]的和可由区间[0,b]的和减去区间[0,a-1]的和得到
但是我们不太可能知道[0,b]，故我们只用知道和b的合并过的区间的左端点就行
其实并查集实质就是一颗树，我们可以以树的角度去看待它，理解维护过程
不理解的同学可以在纸上多划几遍，理解过程
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
const int INF=0x3f3f3f3f;
typedef long long LL;
const int mod=1e9+;
const int maxn=1e5+;
using namespace std; int fa[];//fa[i] 存i的最左端点
int sum[];//记录i到根节点之间和的差值,若再跟节点右侧 则为负数 void init(int n)
{
for(int i=;i<=n;i++)
fa[i]=i;
}
int Find(int x)//带权并查集，此时find不单有查找任务，还有更新距离任务
{
if(x!=fa[x])
{
int t=fa[x];//记录之前的父节点
fa[x]=Find(fa[x]);//路径压缩
sum[x]+=sum[t];//递归维护sum
}//记录到根节点的距离，根节点是一个区间的一个端点而不是一个区间，输入的区间被合并成了两个点
return fa[x];
} int main()
{
#ifdef DEBUG
freopen("sample.txt","r",stdin);
#endif
// ios_base::sync_with_stdio(false);
// cin.tie(NULL); int n,m;
while(~scanf("%d %d",&n,&m))
{
init(n);
memset(sum,,sizeof(sum));
int ans=;
for(int i=;i<=m;i++)
{
int l,r,v;
scanf("%d %d %d",&l,&r,&v);//
int x=Find(l-); //注意为什么要-1
int y=Find(r);
if(x!=y)//如果不是一个集合 合并
{
fa[y]=x;
sum[y]=sum[l-]-sum[r]+v;
}
else if(sum[r]-sum[l-]!=v) ans++;//当有相同的最左端时，直接判断
}
printf("%d\n",ans);
} return ;
}
-