Connect the Dots
Contest: Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
Difficulty rating: 1800
Tags: brute force, dp, dsu, graphs, math, trees

One fine evening, Alice sat down to play the classic game "Connect the Dots", but with a twist.

To play the game, Alice draws a straight line and marks $$$n$$$ points on it, indexed from $$$1$$$ to $$$n$$$. Initially, there are no arcs between the points, so they are all disjoint. After that, Alice performs $$$m$$$ operations of the following type:

- She picks three integers $$$a_i$$$, $$$d_i$$$ ($$$1 \le d_i \le 10$$$), and $$$k_i$$$.
- She selects points $$$a_i, a_i+d_i, a_i+2d_i, a_i+3d_i, \ldots, a_i+k_i\cdot d_i$$$ and connects each pair of these points with arcs.

After performing all $$$m$$$ operations, she wants to know the number of connected components$$$^\dagger$$$ these points form. Please help her find this number.

$$$^\dagger$$$ Two points are said to be in one connected component if there is a path between them via several (possibly zero) arcs and other points.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$).

The $$$i$$$-th of the following $$$m$$$ lines contains three integers $$$a_i$$$, $$$d_i$$$, and $$$k_i$$$ ($$$1 \le a_i \le a_i + k_i\cdot d_i \le n$$$, $$$1 \le d_i \le 10$$$, $$$0 \le k_i \le n$$$).

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the number of connected components.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, there are $$$n = 10$$$ points. The first operation joins the points $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$, and $$$9$$$. The second operation joins the points $$$2$$$, $$$4$$$, $$$6$$$, $$$8$$$, and $$$10$$$. There are thus two connected components: $$$\{1, 3, 5, 7, 9\}$$$ and $$$\{2, 4, 6, 8, 10\}$$$.

In the second test case, there are $$$n = 100$$$ points. The only operation joins the points $$$19$$$, $$$21$$$, $$$23$$$, $$$25$$$, and $$$27$$$. Now all of them form a single connected component of size $$$5$$$. The other $$$95$$$ points form single-point connected components. Thus, the answer is $$$1 + 95 = 96$$$.

In the third test case, there are $$$n = 100$$$ points. After the operations, all odd points from $$$1$$$ to $$$79$$$ will be in one connected component of size $$$40$$$. The other $$$60$$$ points form single-point connected components. Thus, the answer is $$$1 + 60 = 61$$$.

Example input:
3
10 2
1 2 4
2 2 4
100 1
19 2 4
100 3
1 2 5
7 2 6
17 2 31

Example output:
2
96
61

Editorial:
The main idea is to take advantage of the low upper bound of $$$d_i$$$ and apply the Disjoint Set Union.
We will consider $$$dp[j][w]$$$, which denotes the number of ranges that contain the $$$j$$$ node in connection by the triplets/ranges with $$$w$$$ as $$$d$$$ and $$$j$$$ is not $$$a\ +\ k\ *\ d$$$, and $$$id[j][w]$$$, which denotes the node that represents an overall connected component of which $$$j$$$ node is part of for now.
The size of both $$$dp$$$ and $$$id$$$ is $$$max_j * max_w = (n) * 10 = 10\ n$$$.
We will maintain two other arrays, $$$Start\_cnt[j][w]$$$ and $$$End\_cnt[j][w]$$$, which store the number of triplets with $$$j$$$ as $$$a_i$$$ and $$$a_i+k_i*d_i$$$, respectively, and with $$$w$$$ as $$$d_i$$$, to help us maintain the beginning and end of ranges.
We will now apply Disjoint Set Union. For each $$$i$$$th triplet, we assume $$$a_i$$$ will be the parent node of the Set created by $$$a_i$$$, $$$a_i$$$ + $$$d_i$$$, ..., $$$a_i+k_i*d_i$$$.
The transitions of $$$dp$$$ are as follows:
1) if $$$j \ge 10$$$ (max of $$$d_i$$$): for all $$$w$$$, $$$dp[j][w]$$$ are the same as $$$dp[j-w][w]$$$, just with some possible changes. These changes are due to $$$j$$$ being the start or the end of some triplet with $$$d_i$$$ as $$$w.$$$ So, let us start with $$$dp[j][w]$$$ as $$$Start\_cnt[j][w] - End\_cnt[j][w]$$$. If $$$dp[j-w][w]$$$ is non-zero, then perform a union operation (of DSU) between the $$$j$$$ node and $$$id[j-w][w]$$$, increment $$$dp[j][w]$$$ by $$$dp[j-w][w]$$$, and assign $$$id[j][w]$$$ as $$$id[j-w][w]$$$. This unites the ranges over the $$$j$$$ node.
2) if $$$j \lt 10$$$ (max of $$$d_i$$$): we do the same as above; rather than doing for all $$$w,$$$ we would restrict ourselves with $$$w$$$ from $$$0$$$ to $$$j-1$$$.
The net time complexity = updation of $$$dp[j][w]$$$ value by $$$Start\_cnt$$$ and $$$End\_cnt$$$ + union operations due to union of $$$id[j-w][w]$$$ with $$$j$$$ over all $$$w$$$ + incrementing $$$dp$$$ values (by $$$dp[j-w][w]$$$) + copying $$$id$$$ values = $$$10\ n + 10\ nlogn + 10\ n + 10\ n= 10 nlogn + 30n$$$ (in worst case) = $$$O(max_d*n*logn)$$$