Problem 2. Deforestation

USACO 2024 December Contest, Silver

Farmer John 正在扩大他的农场！他已经找到了完美的位置——红黑森林，由数轴上的 $N$ 棵树（$1 \le N \le 10^5$）组成，第 $i$ 棵树位于位置 $x_i$（$-10^9 \le x_i \le 10^9$）。

环境保护法限制了 Farmer John 可以砍伐哪些树来为他的农场腾出空间。有 $K$ 个限制（$1 \leq K \leq 10^5$），规定在线段 $[l_i, r_i]$（包含端点）中必须始终至少存在 $t_i$ 棵树（$-10^9 \le l_i, r_i \le 10^9$）。输入保证红黑森林初始时满足这些限制。

Farmer John 想要他的农场尽可能大。请帮助他计算他可以砍伐的树的最大数量，同时仍然满足所有限制！

输入格式（从终端 / 标准输入读入）：

每个测试点包含 $T$（$1 \le T \le 10$）个独立的测试用例。输入保证一个测试点中的所有 $N$ 之和以及 $K$ 之和均不超过 $3 \cdot 10^5$。

输入的第一行包含 $T$。每个测试用例的格式如下：

第一行包含整数 $N$ 和 $K$。下一行包含 $N$ 个整数 $x_1, \dots, x_N$。以下 $K$ 行，每行包含三个空格分隔的整数 $l_i$，$r_i$ 和 $t_i$。

输出格式（输出至终端 / 标准输出）：

对于每个测试用例，输出一行，包含一个整数，表示 Farmer John 可以砍伐的树的最大数量。

输入样例：

3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4

输出样例：

4
4
3

对于第一个测试用例，Farmer John 可以砍伐前 $4$ 棵树，留下位于 $x_i = 2, 6, 7$ 的树来满足限制。

对于第二个测试用例，额外的限制不会影响 Farmer John 可以砍伐哪些树，因此他可以砍伐相同的树并同时满足两个限制。

对于第三个测试用例，Farmer John 至多只能砍伐 $3$ 棵树，因为初始时有 $7$ 棵树，但第二个限制要求他至少留下 $4$ 棵树不砍伐。

测试点性质： 测试点 2：$N, K \le 16$。测试点 3-5：$N, K \le 1000$。测试点 6-7：对于所有的 $i = 1, \dots, K$ 有 $t_i = 1$。测试点 8-11：没有额外限制。

供题：Tina Wang，Jiahe Lu，Benjamin Qi