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;
}