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