题目详情
返回题库题目描述
来自：USACO 2024 December Contest, Silver
Farmer John 正在扩大他的农场！他已经找到了完美的位置——红黑森林，由数轴上的N棵树（$ 1 \leq N \leq 10^5 $）组成，第ii棵树位于位置 $x_i$（$ -10^9 \leq x_i \leq 10^9 $）。
环境保护法限制了 Farmer John 可以砍伐哪些树来为他的农场腾出空间。有K个限制（$ 1 \leq k \leq 10^5 $），规定在线段$ [ l_i,r_i ] $（包含端点）中必须始终至少存在 $t_i$ 棵树（$ -10^9 \leq l_i,r_i \leq 10^9 $）。输入保证红黑森林初始时满足这些限制。
Farmer John 想要他的农场尽可能大。请帮助他计算他可以砍伐的树的最大数量，同时仍然满足所有限制！
输入描述
每个测试点包含T（$ 1 \leq T \leq 10 $）个独立的测试用例。输入保证一个测试点中的所有N之和以及K之和均不超过 $ 3 \times 10^5 $。
输入的第一行包含T。每个测试用例的格式如下：
- 第一行包含整数N和K。
- 下一行包含N个整数 $ x_1, \dots , x_N $
- 以下K行，每行包含三个空格分隔的整数 $ l_i,r_i,t_i $。
数据范围：
- 测试点 2：$ N,K \leq 16 $。
- 测试点 3-5：0。$ N,K \leq 1000 $
- 测试点 6-7：对于所有的$ i = 1, \dots ,N $, K有 $ t_i = 1 $。
- 测试点 8-11：没有额外限制。
输出描述
对于每个测试用例，输出一行，包含一个整数，表示 Farmer John 可以砍伐的树的最大数量。
提示
对于第一个测试用例，Farmer John 可以砍伐前4棵树，留下位于xi=2,6,7的树来满足限制。
对于第二个测试用例，额外的限制不会影响 Farmer John 可以砍伐哪些树，因此他可以砍伐相同的树并同时满足两个限制。
对于第三个测试用例，Farmer John 至多只能砍伐3棵树，因为初始时有7棵树，但第二个限制要求他至少留下4棵树不砍伐。