п»ї
Фермер Джон расширяет свою ферму! Он определил совершенное место -
Красно-Чёрный Лес, который состоит из \(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\)), указывающих, что должно быть как минимум \(t_i\)
деревьев на отрезке \([l_i, r_i]\), включая конечные точки
(\(-10^9 \le l_i, r_i \le 10^9\)). Гарантируется, что изначально Красно-Чёрный Лес
удовлетворяет этим ограничениям.
ФД хочет чтобы его ферма была как можно большей. Помогите ему вычислить
максимальное количество деревьев, которое он может спилить, удовлетворяя
данным ограничениям.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Каждый ввод состоит из \(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\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите одну строку с целым числом, обозначающим
максимальное количество деревьев, которое может срезать ФД.
ПР�МЕРВВОДА:
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\) дерева не срезанными.
ОЦЕН�ВАН�Е:
- Тест 2: \(N, K \le 16\)
- Тесты 3-5: \(N, K \le 1000\)
- Тесты 6-7: \(t_i = 1\) for all \(i = 1, \dots, N\).
- Тесты 8-11: Нет дополнительных ограничений.
Авторы: Tina Wang, Jiahe Lu, Benjamin Qi