Deforestation

题目描述

农夫约翰正在扩建他的农场！他在红黑森林中找到了一个完美的位置。红黑森林由数轴上的 $N$ 棵树组成（$1 \le N \le 10^5$），第 $i$ 棵树位于位置 $x_i$（$-10^9 \le x_i \le 10^9$）。 环保法规限制了农夫约翰为了给农场腾出空间而可以砍掉哪些树。有 $K$ 条限制（$1 \leq K \leq 10^5$），每条限制规定在线段 $[l_i, r_i]$（包含端点，$-10^9 \le l_i \leq r_i \le 10^9$）中必须始终至少保留 $t_i$ 棵树（$1 \leq t_i \leq N$）。保证红黑森林在初始状态下满足这些限制。 农夫约翰希望把农场做得尽可能大。请帮助他计算：在仍满足所有限制的前提下，他最多能砍掉多少棵树！

输入格式

每个输入包含 $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$。

输出格式

对于每个测试用例，输出一行一个整数，表示农夫约翰最多能砍掉的树的数量。

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

提示

对于第一个测试用例，农夫约翰可以砍掉前 $4$ 棵树，保留位于 $x_i = 2, 6, 7$ 的树以满足限制。 对于第二个测试用例，额外的限制不会影响农夫约翰能砍掉哪些树，因此他可以砍掉相同的树并同时满足两条限制。 对于第三个测试用例，农夫约翰最多只能砍掉 $3$ 棵树，因为最初有 $7$ 棵树，但第二条限制要求他至少保留 $4$ 棵树不被砍掉。 SCORING: Input 2: $N, K \le 16$ Inputs 3-5: $N, K \le 1000$ Inputs 6-7: 对所有 $i = 1, \dots, K$，都有 $t_i = 1$。 Inputs 8-11: 无额外限制。 题目作者：Tina Wang, Jiahe Lu, Benjamin Qi

标签: USACO|2024|Silver

来源

USACO|2024|Silver