Задача №114656. Паразиты в лаборатории
В лаборатории производится селекция новых видов растений. Сейчас в лаборатории есть \(n\) растений. У растения с номером \(i\) концентрация фитогормонов равна \(a_i\). У каждого растения уникальная концентрация фитогормонов, иными словами все числа \(a_i\) различны.
Вам известно, что конкуренты могут проникнуть в лабораторию и заразить растения паразитами, чтобы помешать исследованиям. Паразиты на заражённом растении опасны тем, что сами могут заразить похожие растения. Как только растение с номером \(i\) заражается, паразиты на нём привыкают к концентрации фитогормонов \(a_i\), размножаются и по воздуху заражают все другие растения с номерами \(j\) такие, что \(|a_i - a_j| \le k\), где \(k\) — некоторое заранее известное число.
Для того, чтобы все растения оказались заражены, может быть достаточно посеять паразитов лишь на некоторых растениях, после чего они уже заразят все остальные растения.
Дано несколько запросов (\(l_i, r_i\)), для каждого такого запроса рассматриваются только растения с номерами от \(l_i\) до \(r_i\) включительно. Требуется найти, на какое минимальное количество растений нужно посеять паразитов, чтобы в итоге все растения оказались заражены.
В первой строке заданы три целых числа \(n\), \(q\) и \(k\) (\(1 \le n, q \le 10^6\), \(0 \le k \le 10^9\)) — количество растений в лаборатории, количество запросов и параметр из условия, соответственно.
Во второй строке заданы \(n\) целых чисел \(a_i\) (\(1 \le a_i \le 10^9\)) — концентрации фитогормонов растений. Все \(a_i\) различны .
В каждой из следующих \(q\) строк содержатся по два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)), описывающие очередной запрос.
Для каждого запроса выведите ответ на него — минимальное количество растений, на которое требуется посеять паразитов, чтобы все растения оказались заражены.
Рассмотрим первый пример.
На отрезке \([1, 3]\), есть растения с концентрацими фитогормонов \([1, 3, 5]\). Чтобы заразить их все достаточно посеять паразитов на одно любое из них. Например, если заразить растение с концентрацией фитогормонов \(1\), паразиты на нём размножатся и по воздуху заразят растение с концентрацией фитогормонов \(3\). Паразиты на растении с концентрацией фитогормонов \(3\) в свою очередь тоже размножатся и заразят растение с концентрацией фитогормонов \(5\).
На отрезке \([1, 6]\) также достаточно заразить одно любое растение.
На отрезке \([3, 5]\) для заражения всех растений потребуется посеять паразитов хотя бы на два растения, например на растение с концентрацией фитогормонов \(3\), которое затем заразит растение с концентрацией фитогормонов \(2\) и на растение с концентрацией фитогормонов \(6\). Обратите внимание, что растение с концентрацией фитогормонов \(3\) не сможет заразить растение с концентрацией фитогормонов \(6\) так как \(|3 - 6| = 3 > 2\).
Тесты к этой задаче состоят из девяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(q\) | \(k\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 15 | – | – | \(k \leq 1\) | – | |
| 2 | 5 | – | \(q = 1\) | – | 0 | |
| 3 | 15 | \(n \leq 300\) | \(q \leq 300\) | – | 0 | |
| 4 | 5 | \(n \leq 300\) | – | – | 0, 3 | |
| 5 | 12 | \(n \leq 50000\) | \(q \leq 50000\) | – | 0, 3 | |
| 6 | 12 | \(n \leq 100000\) | \(q \leq 100000\) | – | 0, 3, 5 | |
| 7 | 12 | \(n \leq 300000\) | \(q \leq 300000\) | – | 0, 3, 5, 6 | |
| 8 | 12 | \(n \leq 500000\) | \(q \leq 500000\) | – | 0, 3, 5, 6, 7 | |
| 9 | 12 | – | – | – | 0–8 | Offline-проверка. |
6 5 2 5 1 3 6 2 4 1 3 1 6 3 5 4 5 2 2
1 1 2 2 1
3 3 5 1 12 6 1 3 2 3 1 2
2 2 2