#PU1447. USACO 2024 December Contest, Silver — Problem 2. Deforestation

    ID: 1299 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases线段树二分答案

USACO 2024 December Contest, Silver — Problem 2. Deforestation

USACO 2024 December Contest, Silver — Problem 2. Deforestation

题目描述

Farmer John is expanding his farm! He has identified the perfect location in the Red-Black Forest, which consists of NN trees (1≤N≤1051 \le N \le 10^5) on a number line, with the ii-th tree at position xix_i (−109≤xi≤109-10^9 \le x_i \le 10^9). Environmental protection laws restrict which trees Farmer John can cut down to make space for his farm. There are KK restrictions (1≤K≤1051 \leq K \leq 10^5) specifying that there must always be at least tit_i trees (1≤ti≤N1 \leq t_i \leq N) in the line segment [li,ri][l_i, r_i], including the endpoints (−109≤li≤ri≤109-10^9 \le l_i \leq r_i \le 10^9). It is guaranteed that the Red-Black Forest initially satisfies these restrictions. Farmer John wants to make his farm as big as possible. Please help him compute the maximum number of trees he can cut down while still satisfying all the restrictions!

输入格式

Each input consists of TT (1≤T≤101 \le T \le 10) independent test cases. It is guaranteed that the sums of all NN and of all KK within an input each do not exceed 3⋅1053 \cdot 10^5. The first line of input contains TT. Each test case is then formatted as follows: The first line contains integers NN and KK. The next line contains the NN integers x1,…,xNx_1, \dots, x_N. Each of the next KK lines contains three space-separated integers: lil_i, rir_i and tit_i.

输出格式

For each test case, output a single line with an integer denoting the maximum number of trees Farmer John can cut down.

数据范围

(见题面原文)

样例

样例 1

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
For the first test case, Farmer John can cut down the first $4$ trees, leaving
trees at $x_i = 2, 6, 7$ to satisfy the restriction.
For the second test case, the additional restriction does not affect which trees
Farmer John can cut down, so he can cut down the same trees and satisfy both
restrictions.
For the third test case, Farmer John can only cut down at most $3$ trees because
there are initially $7$ trees but the second restriction requires him to leave
at least $4$ trees uncut.