c/c++语言开发共享HDU 3038 How Many Answers Are Wrong(并查集)

题意

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

思路

sum[x]表示x到区间末尾的总和
则a到b的总和c 可以表示为sum[a]-sum[b+1] = c。

代码

  #include  #include  #include  #include  #include  #define ll long long  using namespace std;    int sum[200009], fa[200009];    int find(int x)  {      if(fa[x] == x)          return x;      int t = fa[x];      fa[x] = find(fa[x]);      sum[x] += sum[t];      return fa[x];  }    void update(int x, int y, int a, int b, int c)  {      if(x > y)      {          fa[y] = x;          sum[y] = sum[a]-sum[b]-c;      }      else      {          fa[x] = y;          sum[x] = sum[b]-sum[a]+c;      }  }    int main()  {      int len, n;      while(~scanf("%d%d", &len, &n))      {          memset(sum, 0, sizeof(sum));          for(int i=0; i<=200001; i++)              fa[i] = i;          int ans = 0;          while(n--)          {              int a, b, c;              scanf("%d%d%d", &a, &b, &c);              b++;              int x = find(a);              int y = find(b);              if(x == y && sum[a] != sum[b] + c)                  ans++;              else if(x != y)                  update(x, y, a, b, c);          }          printf("%dn", ans);      }      return 0;  }