Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2393. Обнуление элементов
Комбинированные алгоритмы (алгоритм Мо)Олимпиадные задачи на русском языке
| 11/04/2018 | Тренировка по алгоритму Мо (B) |
Ограничения: время – 2s/4s, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Имеется массив `a` из `n` неотрицательных целых чисел. Необходимо
для заданной части массива с `i`-го до `j`-го элемента подсчитать минимальное количество действий по обнулению элементов.
Допускаются следующие действия для элементов с `i`-го по `j`-й:
- Заменить любой элемент на 0.
- Заменить два одинаковых элементов на 0 (оба).
Первая строка ввода содержит два целых числа – длину массива `n` и количество запросов `m` (`1\ ≤\ n,\ m\ ≤\ 300000`).
Вторая строка содержит `n` целых чисел в диапазоне от 0 до `10^9` – массив чисел. Следующие `m` строк
содержат по два целых числа `l_j` и `r_j` (`1\ ≤\ l_j\ ≤\ r_j\ ≤\ n`) – запросы на получение количества действия для обнуления элементов
массива с `l_j`-го по `r_j`-й.
Для каждого запроса вывести в отдельной строке минимальное количество действий.
Пример ввода
5 3 3 3 3 3 5 1 5 3 3 3 5
Пример вывода
3 1 2
