hdu 3038(种类并查集)

题目大意：有n次询问，给出a到b区间的总和，问这n次给出的总和中有几次是和前面已近给出的是矛盾的

解题思路：这道题第一次接触很难往并查集方向去思考。这里使用的并查集很灵活，不仅仅要记录其父亲节点，同时还要记录该节点到父亲节点的总和。在更新时，[l,r]要变成[l-1,r]，比如有区间[1,2],[3,4],在更新[3,4]时可以合并成一个完整区间[1,4]，并且在计算[l,r]区间的总和时，是用sum[r] - sum[l-1]来算的。所以这里是用[l-1,r]的原因。

#include<iostream>
#include<cstdio>
#include<cstring>

const int maxn = 200005;
int n,m,ans;
int fa[maxn],rank[maxn];

int find(int x)
{
	if(fa[x] == x) return x;
	int tmp = fa[x];
	fa[x] = find(fa[x]);
	rank[x] += rank[tmp]; 
	return fa[x];
}

void Union(int x,int y,int k)
{
	int fx = find(x);
	int fy = find(y);
	if(fx == fy)
	{
		if(rank[y] - rank[x] != k) ans++;
	}
	else if(fx > fy)
	{
		fa[fx] = fy;
		rank[fx] = rank[y] - rank[x] - k;
	}
	else
	{
		fa[fy] = fx;
		rank[fy] = rank[x] + k - rank[y];
	}
}

int main()
{
	int l,r,k;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i = 0; i <= n; i++)
			fa[i] = i, rank[i] = 0;
		ans = 0;
		for(int i = 1; i <= m; i++)
		{
			scanf("%d%d%d",&l,&r,&k);
			l--;
			Union(l,r,k);
		}
		printf("%d\n",ans); 
	}
	return 0;
}