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("%d\n", ans);
    }
    return 0;
}