CF2020D.Connect the Dots

题意描述

Alice画了一条直线，并在上面标记了 $n$ 个点，从 $1$ 到 $n$ 进行索引。最初，点之间没有连边，所以它们都是不连通的。之后，Alice执行以下类型的 $m$ 个操作：

1. 她选了三个整数 $a_i , d_i , k_i , (1 \le d_i \le 10)$
2. 她选择点 $a_i,a_i+d_i,a_i+2d_i......a_i+k_i \times d_i$，并在每对点之间连边。

在完成所有的 $m$ 次操作后，她想知道这些点形成的连通块$ ^\dagger $的数量。

$ ^\dagger $如果两个点之间通过若干条边（可能为零条）和其他点存在路径，则称这两个点位于一个连通块中。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ 。每个测试用例的描述如下:

每个测试用例的第一行包含两个整数 $n$ 和 $m$ 。
以下 $m$ 行中的第 $i$ 行包含三个整数 $a_i , d_i , k_i , (1 \le a_i \le a_i+k_i⋅d_i \le n, 1 \le d_i \le 10, 0 \le k_i \le n) $ 。

保证所有测试用例中的 $n$ 和 $m$ 之和不超过 $2\times 10^5$。

对于每个测试用例，输出连通块数量。

null