HDU 3038 How many answers are wrong

Description

给出n个数字m次询问

每次询问从L到R这段区间的和

若后面的答案与前面的矛盾，那么后面的答案错误

题目链接

思路

带权并查集，sum[i]表示i到其顶点的距离（两点的差值），也就是[i + 1, pre[i] ]的和

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;

int n, m, ans;
int pre[N];
int sum[N];

void init()
{
    for(int i = 0; i <= n; ++i)
        pre[i] = i;
    memset(sum, 0, sizeof(sum));
}

int found(int x)
{
    if(x == pre[x])
        return x;

    ///路径压缩、权值更新
    int tem = pre[x];
    pre[x] = found(pre[x]);
    sum[x] += sum[tem];
    return pre[x];
}

void unite(int x, int y, int val)
{
    int xx = found(x);
    int yy = found(y);
    if(xx != yy)
    {
        pre[xx] = yy;
        sum[xx] = val + sum[y] - sum[x];///类似向量
    }
    else
    {
        if(sum[x] - sum[y] != val)
            ans++;
    }
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        ans = 0;
        init();
        int L, R, VAL;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &L, &R, &VAL);
            unite(--L, R, VAL);
        }
        cout << ans << '\n';
    }
    return 0;
}