Union-Find Structure

The union-find data structure is a tree-based structure designed to efficiently manage disjoint sets through two primary operations:

• Find Operation: Determines which subset a particular element belongs to
• Union Operation: Merges two subsets into a single set

int parent[N]; // Each element's set identifier, initialized as parent[i] = i

int findRoot(int x) {
    if (x != parent[x])
        parent[x] = findRoot(parent[x]); // Path compression
    return parent[x];
}

void mergeSets(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);
    parent[x] = y; // Attach x's root as child of y's root
}

Weighted Union-Find

This variant uses two arrays: f[n] tracks set membership while d[n] stores weight information between nodes and their parents.

Example Problem: Counting Incorrect Statements

Given a integer sequence of length N, M descriptions are provided sequentially. Each description consists of three integers l, r, s indicating that the sum of elements from position l to r equals s.

For each description, determine if it conflicts with previous statements. Conflicting descriptions are considered incorrect and should be ignored in future evaluations.

Input Format

First line: integers N (sequence length) and M (number of descriptions)
Following M lines: three integers l, r, s per line representing a description

Output Format

Single integer: count of incorrect descriptions

Constraints

• 1 ≤ N ≤ 2×10⁵
• 1 ≤ M ≤ 40000
• 1 ≤ l ≤ r ≤ N
• 1 ≤ s ≤ 2×10⁹
• All subsequence sums fall within [1, 2×10⁹]

Sample Input:

10 5
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1

Sample Output:

1

In this implementation, the union-find stores vectors representing b→a relationships. For a<b, it stores the sum of interval (a,b]; for a>b, it stores the negative sum.

f[b] = a indicates the distance of interval (a,b] is d[b]
When f[c] = b and f[b] = a, d[c] represents (b,c] distance and d[b] represents (a,b] distance.
Path compression updates f[c] = a, making d[c] represent (a,c] distance: d[c] = d[c] + d[b]

During merging where a ≠ b, setting f[b] = a requires updating d[b] using: d[l] + s = d[b] + d[r] (where s is interval (l,r] distance)

#include <iostream>
using namespace std;

const int MAX_N = 2e5 + 10;

int sequenceLength, descriptionCount, leftPos, rightPos, sumValue;
int parent[MAX_N], weight[MAX_N];
int errorCount;

int findParent(int node) {
    if (node != parent[node]) {
        int root = findParent(parent[node]);
        weight[node] += weight[parent[node]];
        parent[node] = root;
    }
    return parent[node];
}

int main() {
    // Initialize parent array
    for (int i = 1; i < MAX_N; i++) 
        parent[i] = i;
    
    cin >> sequenceLength >> descriptionCount;
    
    while (descriptionCount--) {
        cin >> leftPos >> rightPos >> sumValue;
        
        int rootLeft = findParent(leftPos - 1);
        int rootRight = findParent(rightPos);
        
        if (rootLeft == rootRight) {
            // Check for contradiction
            if (weight[rightPos] - weight[leftPos - 1] != sumValue) 
                errorCount++;
        } else {
            // Merge sets and update weights
            parent[rootRight] = rootLeft;
            weight[rootRight] = sumValue + weight[leftPos - 1] - weight[rightPos];
        }
    }
    
    cout << errorCount << endl;
    return 0;
}