Пока некоторые люди страдают от нехватки контестов, я решаю задачки из архивов (:
Сегодня открыл эту задачу: http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=597&chapterid=753#1
Вроде тема курса намекает на то, что ее нужно решать через Range Maximum Query.
Вроде тема курса намекает на то, что ее нужно решать через Range Maximum Query.
Я так и делаю, но что-то не получается.
Кратко опишу свой алгоритм:
1) строим дерево из N элементов (все нули)
2) Каждый запрос, в зависимости от его типа, обрабатываем особым образом:
2.1) Если запрос первого типа, то вызываем RMQ(L,R). Если результат 0, то ни один элемент этого
отрезка не входит ни в одну группу - объединяем.
2.1.1) Что значит объединяем? Всем элементам из данной группы присваиваем одно и то же
значение - номер группы (номер группы - счетчик, увеличиваем его с появлением каждой новой группы)
2.1.2) При каждом изменении значения элемента делаем update данного элемента в дереве.
2.2) Если запрос второго типа, то проверяем:
2.2.1) Если значение элемента - 0, то элемент не принадлежит ни одной группе, выводим "0 0"
2.2.2) Если значение элемента больше 0, то:
2.2.2.1) Проходим вправо - ищем правую границу, попутно обнуляя элементы и делая
update дерева. Аналогично ищем левую границу
2.2.2.2) Выводим границы
2.2.2.2) Выводим границы
Приветствуются прямые указания на ошибки и хорошие тесты, которые завалят программу.
Заранее спасибо!
UPD. со второй операцией ровно та же проблема.
А вот и быдлокод на C++ (форматирование съехало): http://pastebin.com/j2zNEDUv
100000 100000
1 1 100000
2 50000
1 1 100000
2 50000
1 1 100000
2 50000
...
1 1 100000
2 50000
Т.к автор пишет на паскале не думаю что есть возможность воспользоваться C++ сетом
Если вдруг поможет (готовое решение с чистым деревом отрезков) http://pastebin.com/pg13fDgk (хотя тоже на си)
Оно ему, как и freopen'у, сильно не понравилось :D