How Many Answers Are Wrong(权值并查集)详细解释

TT and FF are … friends. Uh… very very good friends -________-b

FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin with, TT should write down a sequence of integers-_-!!(bored).

Then, FF can choose a continuous subsequence from it(for example the subsequence from the third to the fifth integer inclusively). After that, FF will ask TT what the sum of the subsequence he chose is. The next, TT will answer FF’s question. Then, FF can redo this process. In the end, FF must work out the entire sequence of integers.

BoringBoringa very very boring game!!! TT doesn’t want to play with FF at all. To punish FF, she often tells FF the wrong answers on purpose.

The bad boy is not a fool man. FF detects some answers are incompatible. Of course, these contradictions make it difficult to calculate the sequence.

However, TT is a nice and lovely girl. She doesn’t have the heart to be hard on FF. To save time, she guarantees that the answers are all right if there is no logical mistakes indeed.

What’s more, if FF finds an answer to be wrong, he will ignore it when judging next answers.

But there will be so many questions that poor FF can’t make sure whether the current answer is right or wrong in a moment. So he decides to write a program to help him with this matter. The program will receive a series of questions from FF together with the answers FF has received from TT. The aim of this program is to find how many answers are wrong. Only by ignoring the wrong answers can FF work out the entire sequence of integers. Poor FF has no time to do this job. And now he is asking for your help~(Why asking trouble for himself~~Bad boy)
Input
Line 1: Two integers, N and M (1 <= N <= 200000, 1 <= M <= 40000). Means TT wrote N integers and FF asked her M questions.

Line 2…M+1: Line i+1 contains three integer: Ai, Bi and Si. Means TT answered FF that the sum from Ai to Bi is Si. It’s guaranteed that 0 < Ai <= Bi <= N.

You can assume that any sum of subsequence is fit in 32-bit integer.
Output
A single line with a integer denotes how many answers are wrong.
Sample Input
10 5
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1
Sample Output
1

这道题目是一道权值并查集的经典题目 说实话 很不好理解 我看了网上很多博主的解释 都没有把这个题目里面的精髓讲清楚 在这里感谢泰泰学长的讲解(tql)！

首先我们要明确题解中各个变量的意义 pre数组不用说了 重点在于sum数组 这就是我们权值并查集所维护的值 用一张图片解释下什么是sum数组 其实就是子节点与父节点的区间权值

大家不要在意这个图片的质量 理解就好，

接下来我们要确定这道题的思路 首先我们得到了两个区间值和一个权值 这个权值就是就是区间的权值 然后我们去判断这两个区间值是否属于一个集合 如果属于一个集合 意味着他们拥有相同的祖先 这时我们又知道这两个区间值节点之间距离的权值 所以我们就可以去判断所给的操作是否正确

if(sum[A]-sum[C]!=val)
ans++;
1
2

再就是如果这两个区间值的根节点不相同 这是一种怎么样的情况 这也是这道题最不好理解的地方 我们来仔细想想 如果根节点不同 意味着我们有了两个集合 我们需要把这两个集合合并 很好理解两个集合都可以被抽象为一个叶子节点和一个根节点 我们首先要把这两个集合联系起来 然后我们会发现 当联系起两个集合以后 一个根节点还是根节点 也就是说sum还是0 但另一个有了根节点 于是我们就需要去更新这个点的sum值

A,B 与 C,D 为两个集合 以上就是合并以后它们的关系 可以做一个想象 左手捏住这个矩形的左上角 右手捏住右下角 轻轻一拉 会有意想不到的理解

这是代码的表示

pre[D]=B;
sum[D]=sum[A]+val-sum[C];
1
2

至此 这道题目就迎刃而解了 以下是AC代码

#include<iostream>
#include<csdio>
using namespace std;
int pre[200000+10];
int sum[200000+10];
int find(int i)
{
    if(pre[i]==i) return i;
    int tmp=pre[i];
    pre[i]=find(pre[i]);
    sum[i]+=sum[tmp];        //路径压缩  我们需要上面所有结点的值
    return pre[i];
}

int m,n;
int tmp,tmpa,tmpb;
int main()
{
    while(~scanf("%d %d",&m,&n))
    {
        int ans=0;
        for(int i=0;i<=m;i++)
        {
            pre[i]=i;
            sum[i]=0;
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d %d %d",&tmpa,&tmpb,&tmp);
            tmpa--;
            int aa=find(tmpa);
            int bb=find(tmpb);
            if(aa!=bb)
            {
                pre[bb]=aa;
                sum[bb]=sum[tmpa]+tmp-sum[tmpb];//
            }
            else
            {
                if(sum[tmpb]-sum[tmpa]!=tmp)
                {
                    ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

这道题目在我看来真的不好理解 很抽象 问题的关键在于sum数组的使用 我认为这类题目的关键在于脑子里或者稿纸上要有一个图的模型 然后我们才能去真正意义上的理解题目 进而AC