区间和探测（带权并查集）

题目：

给出区间[1,n],下面有m组数据，l r v区间[l,r]之和为v,每输入一组数据，判断此组条件是否与前面冲突,如果与前冲突，则视为无效数据。

请统计与前面冲突的数据的个数。

输入

输入两个整数n(1 le n le 2*10^5), m(1 le m le 4*10^4)n(1≤n≤2∗105),m(1≤m≤4∗104)。

接下来m行，每行给出三个整数l, r, v (1 le l le r le n, 1 le v le 10^9)l,r,v(1≤l≤r≤n,1≤v≤109)。

输出

输出冲突数据的个数。

样例

输入

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

输出

1

---

代码：

/*************************************************************************
 > Author: Henry Chen
 > Mail: 390989083@qq.com 
 > Created Time: 日  8/23 22:50:02 2020
 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;
int f[200009],sm[200009];
int find(int x)
{
 if(f[x] == x) return x;
 int k = find(f[x]);
 sm[x] += sm[f[x]];
 return f[x] = k;
}
int main()
{
 int n,m;
 cin >> n >> m;
 for(int i = 1;i <= n;i++)
 {
  f[i] = i;
 }
 int ans = 0;
 for(int t = 1;t <= m;t++)
 {
  int l,r,v;
  scanf("%d%d%d",&l,&r,&v);
  find(l-1);
  find(r);
  if(f[r] == f[l-1])
  {
   if(sm[r] - sm[l-1] != v)
   {
    //printf("%d %d
%d %d
",l-1,f[l-1],r,f[r]);
    //printf("
*********%d*********

",t);
    ans ++;
   }
  }
  else
  {
   if(f[l-1] > f[r])
   {
    sm[f[l-1]] = -sm[l-1]-v+sm[r];
    f[f[l-1]] = f[r];
   }
   else
   {
    sm[f[r]] = v+sm[l-1]-sm[r];
    f[f[r]] = f[l-1];
   }
  }
  /*puts("");
  for(int i = 0;i <= n;i++)
  {
   printf("%d ",f[i]);
  }
  puts("");
  for(int i = 0;i <= n;i++)
  {
   printf("%d ",sm[i]);
  }
  puts("");*/
 }
 cout << ans << endl;
 return 0;
}