欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HDU 3038 How Many Answers Are Wrong(并查集)

程序员文章站 2022-04-15 11:04:16
题意 有n次询问,给出a到b区间的总和,问这n次给出的总和中有几次是和前面已近给出的是矛盾的。 思路 sum[x]表示x到区间末尾的总和 则a到b的总和c 可以表示为sum[a]-sum[b+...

题意

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