Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2232. Подсчет пингвинов
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (F) |
| 14/07/2016 | Лето 2016 - 9 (C) |
Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для наблюдения за пингвинами Том установил в ущелье камеры.
Время от времени с камер поступает информация о передвижениях пингвинов,
и иногда Том делает запросы о количестве стай пингвинов на некотором участке ущелья.
Стаей считается последовательность пингвинов без промежутков, отделенная пустым пространством от других стай.
Первая строка ввода содержит два целых числа `n` (длина ущелья) и `m` (`1\ ≤\ n\ ≤\ 100000`,`1\ ≤\ m\ ≤\ 100000`).
Далее следует `m` строк, содержащих хронологически упорядоченную последовательность запросов Тома
и поступлений информации с камер.
Первым символом в строке указывается символ '?', '*' или '.', за
которым через пробел следуют два числа `p_1` и `p_2` (`1\ ≤\ p_1\ ≤\ p_2\ ≤\ n`), задающих участок ущелья.
Cимвол '?' означает запрос Тома о количестве стай пингвинов на участке.
Cимвол '*' означает, что все позиции на заданном участке заполнились пингвинами,
символ '.' означает, что все позиции на заданном участке стали свободными.
Первоначально все позиции в ущелье свободны.
Для каждого запроса Тома вывести на отдельной строке количество стай пингвинов, которые видны полностью
или частично на заданном участке ущелья.
Пример ввода
10 5 * 1 7 . 3 5 ? 2 7 * 4 4 ? 1 10
Пример вывода
2 3
