欢迎访问~原文出处——

---

---

题意概括

　　有一个序列，共n个数，可正可负。

　　现在有m个结论。n<=200000,m<=40000

　　每个结论包括3个数a,b,s，表示序列中a~b的区间和为s。

　　现在让你依次判断结论的正确性。

　　如果当前结论与之前的矛盾，那么ans++，忽略该结论。

　　注意多组数据。

---

 

题解

　　这个差不多是带权并查集的板子题了……应该不用多说了。。

---

 

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=200005;int n,m,fa[N],val[N];int getf(int k){	if (fa[k]==k)		return k;	int res=getf(fa[k]);	val[k]+=val[fa[k]];	return fa[k]=res;}int main(){	while (~scanf("%d%d",&n,&m)){		for (int i=0;i<=n;i++)			fa[i]=i,val[i]=0;		int ans=0;		while (m--){			int a,b,s;			scanf("%d%d%d",&a,&b,&s);			a--;			int Fa=getf(a),Fb=getf(b);			if (Fa==Fb)				ans+=(val[a]-val[b])!=s;			else {				fa[Fa]=Fb;				val[Fa]=-val[a]+s+val[b];			}		}		printf("%d\n",ans);	}	return 0;}